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

Question

波波老师，今天在做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)
我看了下网上很多的答案解析都是这样定义的，我实在有些困惑，波波老师您可以帮帮我嘛？

Answer 1

liuyubobobo 2020-05-25 15:26:53

我觉得你下面的回复状态理解方式非常对：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 可以看做是不持股，且在冷冻期。

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

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

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

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

加油！：）

• 提问者 v不离不弃v #1

  老师，我又有些疑问：
  （1）对于理解为cooldown：dp[i][2]=dp[i-1][1]+prices[i],如果是在前一天持有并且当天卖了，day[i]才会进入冷冻，那么资金的第i天（冷冻的这一天）的剩余资金不应该是：dp[i-1][1]的资金 +prices[i - 1]（卖掉的当天的资金）嘛，这里我有些困惑，为啥是prices[i]呢？
  
  （2）还有一个就是，对于买（持有）来说，题目的意思就是我们只能分成3种情况才可以在day[i]买入：1.day[i-1]啥都不干（既没有买也没有卖，空着手）。 2. day[i-1]天是冷冻期（因为在day[i-2]天卖了，此时就回到了啥都没有状态，冷冻期过了之后就可以买）。3.day[i-1]天本来就是已经保持买入状态，那么day[i]天依然保持,这样理解的话不就还因该加上冷冻期这个时候的资金状态来判断max么？为啥正确的答案是不需要考虑冷冻期的资金呢？我感觉如果仔细思考的话真的是越来越不理解了，感觉这个题目有问题。。。。哎，难受哇。。
  
  感觉买股票的问题需要对这个问题理解的很透彻才行，因为需要考虑很多个变量的安排合理性，但是我始终感觉出题者想要我们干的事（目的）就是固定的（即他在出题的时候考虑的解答思路就是固定的某个），但是如果让一个解题者考虑，那么因为考虑角度的不同可能会产生一定的问题，但是从这种理解上却又是可行的，但是又违背了出题者的本意和思路。我不知道这题该怎么办了-。-

• 提问者 v不离不弃v #2

  波波老师，我和同学想出了一个不考虑这么多因素的解法（2个因素：0 不持有，1持有），我个人觉得是普通大众最可以理解的方法了，您看看这个解法好不好-。-我觉得网上考虑的条件作为一个初学者我真的感觉考虑不到这么多，但是我个人觉得这个方法是最最好理解的了，您可以帮我看看嘛，如果好的话，希望可以提供给这里的同学-。-
  class Solution {
      public int maxProfit(int[] prices) {
          if (prices.length <= 1) return 0;
          int unhold = 0;
          int hold = -prices[0];
          int pre = 0;
          for (int i = 1; i < prices.length; i++) {
              int temp = unhold;
              unhold = Math.max(unhold, hold + prices[i]);
              hold = Math.max(hold, pre - prices[i]);
              pre = temp;
          }
          return unhold;
      }
  }

• liuyubobobo 回复 提问者 v不离不弃v #3

  对于（1）dp[i][2] 表示的是第 i 天卖掉。要想在第 i 天卖掉，需要第 i-1 天是持有；卖出的价格是 price[i]。用具体的一个小的测试用例实际理解一下？；对于（2）“这样理解的话不就还因该加上冷冻期这个时候的资金状态来判断max么？”这句话我没有特别理解。你的意思是代码需要加上哪一行？还是怎么修改？

点开查看后面6条评论

Answer 2

提问者 v不离不弃v 2020-05-24 10:24:20

（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]);

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

Answer 3

提问者 v不离不弃v 2020-05-24 04:50:04

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

Answer 4

提问者 v不离不弃v 2020-05-24 04:49:02

波波老师我感觉我思考方式有点问题，有个链接是

可以用这样的一个状态转换图表示

用数组 s0 表示第 i 天 rest 后得到的 max profit

用数组 s1 表示第 i 天 buy 后得到的 max profit

用数组 s2 表示第 i 天 sell 后得到的 max profit

根据状态转换图的递推关系

s0[i] = max(s0[i - 1], s2[i - 1])

      = max(  hold   ,   rest   ) 

s1[i] = max(s1[i - 1], s0[i - 1] - prices[i])

      = max(  hold   ,        buy in        ) 

s2[i] = s1[i - 1] + prices[i]

这样一想就想通了但是就是不知道为啥不考虑cooldown的问题了。。。