[刷题]leetcode #309 - Best Time to Buy and Sell Stock with Cooldown

题目

代码

class Solution {public int maxProfit(int[] prices) {if (prices.length <= 1) return 0;int l = prices.length;int a=0, b = -prices[0], c = 0;for (int i = 1; i < l; ++i){int temp = a;a = Math.max(a, c);c = b + prices[i];b = Math.max(b, temp - prices[i]);}return Math.max(a, c);}
}

解析

原解答：Knowledge Center-Best Time to Buy and Sell Stock with Cooldown | LeetCode 309 | C++, Java, Python

首先请看下图，在此图中我们定义三种状态，A，B，C，分别代表：

• A：可以买进股票的状态；
• B：已购入股票的状态；
• C：刚卖完股票，还没有经过冷却期的状态

并且定义了三种行为：hold，buy，sell：

• hold：什么也不干
• buy：买进股票
• sell：卖出股票

结合三种状态和三种行为的解释，下面的状态转移图不难理解。

在任何一天中，我们只能处于上述三种状态中的任何一种，并且只能采取三种行为中的任何一种，由此进入下一天的状态中。

我们以题目所给的例子为例：prices: [1, 2, 3, 0, 2]，首先画出如下的图，横列表示prices，纵列表示三种状态。

假设在第一天之前（假设为第0天），我们处于A状态，初始利润为0.

那么，在第一天，如果我们要处于A状态，只能选择hold，此时不赚不亏，所以利润相应更新为 $0+0=0$。如果在第一天要处于B状态的话，需要采取buy的行动，这一行动带来的利润为-1（也就是-当前价格），所以利润相应更新为 $0+(-1)=-1$。并且在第一天我们无法处于C状态，所以在第一天所代表的纵列，我们可以填上如下的数字：

接着我们来分析第二天，第二天的分析方法也和第一天一样：

在第二天，如果要到达A状态的话，可以由第一天A状态 $\rightarrow$hold或者第一天C状态 $\rightarrow$hold

• 如果是第一天A状态 $\rightarrow$hold，那么这个过程利润会更新为：profit1 = 0 + 0
• 如果是第一天C状态 $\rightarrow$hold，呢么这个过程利润会更新为：profit2 = 0 + 0
• 我们取max(prifit1, profit2),也就是0.(为什么要取最大值呢，我的理解是，在后面我们也会进行相似的计算，只有在当前时间节点的利润达到更大，后续时间节点的利润才会更大。)

在第二天，如果要到达B状态的话，可以由第一天A状态 $\rightarrow$buy或者第一天B状态 $\rightarrow$hold

• 如果是第一天A状态 $\rightarrow$buy，那么这个过程利润会更新为：profit1 = 0 + (-2)
• 如果是第一天B状态 $\rightarrow$hold，呢么这个过程利润会更新为：profit2 = -1 + 0
• 我们取max(prifit1, profit2),也就是-1.

在第二天，如果要到达C状态的话，只能由第一天B状态 $\rightarrow$sell

• 这个过程利润会更新为：profit = -1 + 2
• 我们取1.

经过上述过程，上面的表可以做如下更新：

重复做这样的计算，我们把上面的表填满，得到：

我们只需要在最后一个纵列中选出所标出的两个数中的最大值作为输出即可。一个小细节是为什么不考虑中间那个值（也就是1）呢？因为要到达B状态只有buy或者hold，而当到达最后一天的时候，我们如果可以sold的话肯定选择sold，不能sold的话肯定选择hold，总之不可能选择继续buy，因为buy这个动作肯定亏钱，所以中间的数字不做考虑。程序如上。