关于leetcode309题的一个小疑惑（java）

来源：9-4 状态的定义和状态转移 House Robber

v不离不弃v

2020-05-24

波波老师，今天在做309题的时候，然后题目做完了，在想优化解法的时候突然有个问题把我搞懵逼了，您可以帮我看看嘛？309题的思路我先说下：
dp[i][j]表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益。
这里 j 取三个值：
0 表示不持股；
1 表示持股；
2 表示处在冷冻期。

一、不持股可以由这两个状态转换而来：（1）昨天不持股，今天什么都不操作，仍然不持股。（2）昨天cooldown，今天任然不做任何操作
二、持股可以由这两个状态转换而来：（1）昨天持股，今天什么都不操作，仍然持股；（2）昨天不持股，今天买了一股；
三、cooldown:前一天股票卖了，今天冷冻
代码如下：

dp[i][0]=max(dp[i-1][0],dp[i-1][2])
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2]=dp[i-1][1]+prices[i]

这里是AC了，但是我在想优化空间的时候，突然想到一个问题：

dp[i][2]=dp[i-1][1]+prices[i]

对于第i天的cooldown，题目的意思是必须前一天卖出，今天【i】cooldown，也就是说，必须前一天的前一天【i-2】持有，前一天【i-1】卖出，今天【i】cooldown，那么这里这样写不就错了么？这里的意思分明是昨天【i-1】持有，今天【i】卖出后就只是今天cooldown。但是题目上是这样的：After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
我看了下网上很多的答案解析都是这样定义的，我实在有些困惑，波波老师您可以帮帮我嘛？

写回答

4回答

liuyubobobo

2020-05-25

我觉得你下面的回复状态理解方式非常对：0：啥都不操作 1：买（持有） 2：卖出

但如果使用冷冻期理解，我觉得也没有问题。

其实 dp[i][2]=dp[i-1][1]+prices[i] 的本质就是：在 i - 1 天，你还持有着股票，所以才能卖，卖了以后获得了 price[i] 的钱。

反过来想：dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
这句话中 dp[i-1][0]-prices[i] 的意思就是，只有你在不持股且不是冷冻期的状态下，才能买股票。买股票花费 price[i] 的钱。

状态 2 可以看做是不持股，且在冷冻期。

因为有冷冻期的概念，所以不持股的状态分成了两部分：不持股且在冷冻期和不持股没有在冷冻期。再加上持股的状态。所以整体有三个状态。我觉得还算自然。

正因为如此，我觉得你设想的只区分持股不持股，是不行的，就是因为有冷冻期的存在。

不知道我这么解释，你能不能想通？

不管怎样，这样一个问题，经过你这样的思考，我相信你的理解肯定已经更深刻了：）

加油！：）

liuyubobobo

v不离不弃v

这个问题三个状态如果实在绕不过来，试试能不能理解我的这两个状态的解法：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/cpp-0309/main2.cpp 加油！：）

2020-05-26

共9条回复

v不离不弃v

提问者

2020-05-24

（1）对于如下方程：

dp[i][0]=max(dp[i-1][0],dp[i-1][2])
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2]=dp[i-1][1]+prices[i]

对于这个方程的话，如果理解为

0：啥都不操作 1：买（持有） 2：卖出 ------>就对了，

0（啥都不做）可以由：day[i - 1] 啥都不做 or day[i - 1] cooldown 得到

1（买）可以由:day[i - 1] 已经买 or day[i - 1] 啥都不干得到

2（卖出）可以由 day[i - 1] 已经买入再卖掉得到

但是对于这个问题的思考，对于cooldown这个条件很难将其归结到 0 中（啥都不做），很多人会将其单独考虑，但是我觉得貌似太难想到了。

（2）我想了一个之定义2个状态的方程

0：不持有

1：持有

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);

dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);

但是不知道初始化咋弄-。-但是我个人觉得貌似是完全可以的，我再想想初始化的定义~~~

v不离不弃v

提问者

2020-05-24

感觉还是理解方式的问题，这个方程感觉是没问题的，但是就是不知道咋思考了，就是每个方程所代表的意思我觉得我可能理解的不到位，如果换成如下的理解：观望，买，卖，肯定是对的，但是这似乎很难理解，因为我们在解题的时候是无路如何也没办法忽视cooldown这个条件的，将cooldown归结到观望中还是感觉太难想到了。。。。