309. 最佳买卖股票时机含冷冻期 (opens new window)

1.动态规划

思路：股票类型的题目通法就是从状态机入手,这也是思考动态规划的状态转移方程需要考虑的。

定义dp[ i ] [ j ]表示前i个股票，状态为j的最大利润值。其中对于每个i时刻，j只可能包含两个状态，分别是持有股票和不持有股票。接下来考虑下面的状态机：

• 当前不持有股票下，最大利润可能来源于以下任意一种状态，因此状态转移方程：

  dp[ i ] [ 0]=Math.max(dp[ i-1 ] [ 0]，dp[ i -1] [ 1]+prices[ i ])

  • 延续第i-1时刻不持有股票的状态，不出手，摆烂放空
  • 将i-1时刻持有的股票在i时刻卖掉

• 当前持有股票的情况下，状态转移方程：

  dp[ i ] [ 1]=Math.max(dp[ i-1 ] [ 1]，dp[ i-2 ] [ 0]-prices[ i])

  • i时刻持有的股票在i-1时刻已经存在，因此第i时刻不出手，继续摆烂放空
  • i时刻持有的股票是在i时刻购买的，因为有冷冻期，因此计算当前存款应该从 i -2时刻的总价扣除。

注意：购买股票时，并不需要关注i-2时刻是否有卖出股票，然后分类讨论当前总价是拿i-1时刻还是i-2时刻进行计算。假设从i-1时刻卖了股票，那么用i-2时刻计算没有问题；而如果i-1时刻没有卖股票，并且不持有股票，那么此时i-1状态的利润只能够从i-2时刻不持有股票的状态转移得来。

剪枝：注意一定要剪枝，否则同一个时刻的同一个状态会被计算多次导致超时。只要当前时刻状态的最大利润计算过了(不为初始值)，那么直接返回。

本题写法是从后向前遍历，因此既要递归遍历子状态，又要更新到dp数组中。实际上本题也可以不用递归，正向遍历。

class Solution {
    int[][] dp;
    public  int maxProfit(int[] prices) {
        dp=new int[prices.length][2];
        for(int i=0;i<prices.length;i++){
            Arrays.fill(dp[i],Integer.MIN_VALUE);
        }
        if(prices.length<3){
            if(prices.length==1) return 0;
            return Math.max(0,prices[1]-prices[0]);
        }
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[1][0]=Math.max(0,prices[1]-prices[0]);
        dp[1][1]=-Math.min(prices[0],prices[1]);
        dfs(prices,prices.length-1,0);
        return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
    }
    public  int dfs(int[] prices,int index,int hold){
        if(index<2){
            return dp[index][hold];
        }
        //剪枝
        if(dp[index][hold]!=Integer.MIN_VALUE){
            return dp[index][hold];
        }
        if(hold==1){
            return dp[index][hold]=Math.max(dfs(prices,index-1,hold),dfs(prices,index-2,0)-prices[index]);
        }
        else {
            return dp[index][0]=Math.max(dfs(prices,index-1,0),dfs(prices,index-1,1)+prices[index]);
        }
    }
}