买卖股票的最佳时机含冷冻期

问题：

给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

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

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

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

示例：

示例 1:

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

示例 2:

输入: prices = [1]
输出: 0

思路：

典型的动态规划问题，其中dp数组记录股票交易中的三种状态。

dp[i][0]对应当前持有股票时的最大累计收益。

dp[i][1]对应当前不持有股票且在冷冻期的最大累计收益。

dp[i][2]对应当前不持有股票且不在冷冻期的最大累计收益。

代码：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        //动态规划数组记录三种状态
        int[][] dp = new int[n][3];
        /*
        dp[i][0] -> 当前持有股票的最大收益
        dp[i][1] -> 当前不持有股票且在冷冻期的最大收益
        dp[1][2] -> 当前不持有股票且不在冷冻期的最大收益       
         */
         dp[0][0] = -prices[0];
         for(int i = 1; i < n; i++){
             dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
             dp[i][1] = dp[i-1][0] + prices[i];
             dp[i][2] = Math.max(dp[i-1][1],dp[i-1][2]);
         }
         return Math.max(dp[n-1][1],dp[n-1][2]);
    }
}