题目描述

题解

动态规划

这道题是第二道股票题的拓展, 在第二道题的基础上增加了冷冻期的设定. 由此持有股票的状态多了一个, 由原来的持有股票和不持有股票添加了一个冷冻期的状态.

状态定义

用dp[i][j]表示在第 i 天 j 状态下所获得的最大收益, 其中:

当j为0: 表示不持股

当j为1: 表示持股

当j为2: 表示处于冷冻期

状态转换

当j=0时转换方程没有变化, 依然是维持上一个不持股状态或者将前一天的股票抛出

当j=1时状态方程就要改变了, 因为加入了冷冻期所以要么维持上一天的持股状态或者将上一天的冷冻期状态转换过来

当j=2时令其等于dp[i-1][0]即可

初始值

dp[0][0]=0

dp[0][1]=-prices[i]

dp[0][2]=0或者负无穷均可

public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len < 2) {
        return 0;
    }

    int[][] dp = new int[len][3];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[0][2] = 0;

    for (int i = 1; i < len; i++) {
        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 - 1][2] - prices[i]);
        dp[i][2] = dp[i-1][0];
    }

    return dp[len - 1][0];
}