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

思路

运用动态规划处理

1.定义dp数组

在之前没过渡期时是买入和卖出两个状态，因为有过渡期了，所以就是三个状态，买入，卖出，过渡期。

dp[i][0]表示第i天持有股票的价值。可能i-1天就已经买入了。

dp[i][1]表示第i天不持有股票的价值且非过渡期。

dp[i][2]表示第i天是过渡期。

如果按照上面的定义的话，递推公式就会面临一个问题：dp[i][1]如何定义?第i天是非过渡期且不持有股票的价值就应该是前一天是过渡期和前两天卖出以及前一天不持有中取最大的，但是前两天不持有可能前两天的第一天是过渡期或者前两天就是不持有。无法用上面的定义表示。所以需要再次将状态2细分。

dp[i][0]表示第i天持有股票的价值。可能i-1天就已经买入了。

dp[i][1]表示度过过渡期后不持有股票的价值，即前2天卖出股票的价值。

dp[i][2]表示第i天卖出股票后的价值

dp[i][3]表示第i天是过渡期。

2.递推公式

     dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));     dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);     dp[i][2] = dp[i-1][0]+prices[i];     dp[i][3] = dp[i-1][2];

3.初始化

        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;

4.遍历顺序

根据递推公式可以知道，是从后向前遍历数组，所以就是正序遍历

5.打印数组 

从不持有股票的三种情况中取最大的即可。

代码

class Solution {    public int maxProfit(int[] prices) { int dp[][] = new int[prices.length][4]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; dp[0][3] = 0; for(int i =1;i<prices.length;i++){     dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));     dp[i][1] = Math.max(dp[i-1][1],dp[i-1][3]);     dp[i][2] = dp[i-1][0]+prices[i];     dp[i][3] = dp[i-1][2]; } return Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));    }}