本文共 1220 字，大约阅读时间需要 4 分钟。

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:

输入: [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路：

1、本文对状态的定义和状态转移可能有一些别扭。

2、我对冷冻期的处理是：只要不持股过了一天，就一直处于冷冻期，直到再购入股票为止。

3、如果对这一点理解上有困难的朋友，不是你们的问题哈。不用纠结我的做法，我认为只要是状态定义准确，状态转移方程正确即可，具体细节上不一定跟我一样，以能通过系统测评为准。

这道题增加了冷冻期这样一个条件，也没有限制多少笔交易。因此只需要增加一个状态（表示处在“冷冻期”）即可。

注意：这里是增加一个状态，不是增加一维状态。

第 1 步：状态定义

dp[i][j] 表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益。

这里 j 取三个值：

0 表示不持股；

1 表示持股； 2 表示处在冷冻期。 第 2 步：状态转移方程

• 不持股可以由这两个状态转换而来：（1）昨天不持股，今天什么都不操作，仍然不持股。（2）昨天持股，今天卖了一股。
• 持股可以由这两个状态转换而来：（1）昨天持股，今天什么都不操作，仍然持股；（2）昨天处在冷冻期，今天买了一股；
• 处在冷冻期只可以由不持股转换而来，因为题目中说，刚刚把股票卖了，需要冷冻 1 天。
  上面的分析可以用下面这张图表示：
  

与之前股票问题的不同之处只在于：

从不持股状态不能直接到持股状态，得经过一个冷冻期，才能到持股状态。

第 3 步：思考初始化

在第 0 天，不持股的初始化值为 0，持股的初始化值为 -prices[0]（表示购买了一股），虽然不处于冷冻期，但是初始化的值可以为 0。

第 4 步：思考输出

每一天都由前面几天的状态转换而来，最优值在最后一天。取不持股和冷冻期的最大者。

代码：

class Solution {
       public int maxProfit(int[] prices) {
           if(prices == null || prices.length <= 1){
               return 0;        }        int n = prices.length;        int[][] dp = new int[n][3];        dp[0][0] = 0;        dp[0][1] = -prices[0];        dp[0][2] = 0;        for(int i=1; i

转载地址：http://fpwpi.baihongyu.com/