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

一. 题目

二. 思路--动态规划

我把每天的持股状态分为四种,那么每天的收益情况就分为四种,这里就用二维dp数组来保存了
dp[i][j],i为天数,j为每天的状态 dp[i][j]各状态存最大收益

• j=0不持股,当天没卖出(说明本就不持股,前面就卖了)
• j=1不持股,当天卖了(前一天是持股状态)
• j=2持股,当天买了(前一天持股,为什么这里没有前一天没持股且没卖?因为由于冷却器存在,当天买了说明前一天没卖)
• j=3持股,当天没买(要么是前一天买的,要么是前一天本就持有的)

三. 代码:

class Solution {
    public int maxProfit(int[] prices) {
        final int len = prices.length;
        //没有买卖机会
        if (len <=1){
            return 0;
        }

        //每天的持股状态dp[i][j],i为天数,j当前状态 dp[i][j]各状态存最大收益
        // j=0不持股,当天没卖出(本就不持股,之前就卖的)
        // j=1不持股,当天卖了
        // j=2持股,当天买了(注意由于冷却器存在,当天买了说明前一天没卖)
        // j=3持股,当天没买(要么是前一天买的,要么是前一天本就持有的)
        int[][] dp=new int[len][4];

        //初始化
        dp[0][0]=0;//本来就不持有，啥也没干
        dp[0][1]=0;//可以理解成第0天买入又卖出，那么第0天就是“不持股且当天卖出了”这个状态了，其收益为0，所以初始化为0是合理的
        dp[0][2]=-1*prices[0];//第0天只买入,负收益
        dp[0][3]=-1*prices[0];//当前的持股收益,负收益

        for (int i = 1; i < len; i++) {
            //前一天就不持股
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            //前一天持股的收益+今天卖出的收益
            dp[i][1]=Math.max(dp[i-1][2],dp[i-1][3])+prices[i];
            //前一天可能不持股(非当天卖的)或者持股
            dp[i][2]=Math.max(dp[i-1][0],dp[i-1][3])-prices[i];
            //要么是前一天买的,要么是前一天本就持有的
            dp[i][3]=Math.max(dp[i-1][2],dp[i-1][3]);
        }


        return Math.max(Math.max(dp[len-1][0],dp[len-1][1]),Math.max(dp[len-1][2],dp[len-1][3]));
    }
}