123. 买卖股票的最佳时机 III (opens new window)

1.动态规划+状态机

当前利润在计算时涉及到以下几个问题：

• 当前是第几次成交，后面是否还可以继续交易？
• 当前可以买股票，还是只能够买股票？

因此根据①当前成交次数②当前是否持有股票可以划分成6个状态(实际上有两个状态可以省略)。另外注意考虑每个状态的初始化时机，比如状态3只有在第三天的时候买入股票，才能进行初始化。每个状态的转换只与前一天的状态有关，因此可以优化为常数空间。

✨除了总数，方案数以外，状态机的思想在动态规划里也很重要。

class Solution {
    public int maxProfit(int[] prices) {
        //状态0：不持有股票 成交数0
        //状态1：持有股票   成交数0
        //状态2：不持有股票 成交数1 --至少i=1才能够初始化
        //状态3：持有股票   成交数1 --至少在i=2才能初始化
        //状态4：不持有股票 成交数2 --至少i=3才能初始化
       long[][] dp=new long[prices.length][5];
       dp[0][0]=0;
       dp[0][1]=-prices[0];
       dp[0][2]=Integer.MIN_VALUE;
       dp[0][3]=Integer.MIN_VALUE;
       dp[0][4]=Integer.MIN_VALUE;
        for(int i=1;i<prices.length;i++){
            dp[i][0]=0;
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        int res=0;
        res=Math.max(res,(int)dp[prices.length-1][2]);
        res=Math.max(res,(int)dp[prices.length-1][4]);
        return res;
    }
}

188. 买卖股票的最佳时机 IV (opens new window)

2.翻译一维dp

技巧：金额采用int类型保存，将非法类型置为Integer.MIN_VALUE/2。否则需要像上面一样用long类型保存。

class Solution {
    public int maxProfit(int k, int[] prices) {
        //0未持有，1持有股票
        int[][] dp=new int[k+1][2];
        dp[0][1]=-prices[0];
        for(int i=1;i<k;i++){
            Arrays.fill(dp[i],Integer.MIN_VALUE/2);
        }
        for(int i=1;i<prices.length;i++){
            for(int j=k;j>=1;j--){
                dp[j][1]=Math.max(dp[j][1],dp[j][0]-prices[i]);
                dp[j][0]=Math.max(dp[j][0],dp[j-1][1]+prices[i]);
            }
            dp[0][1]=Math.max(dp[0][1],-prices[i]);
        }
        int res=0;
        for(int i=1;i<=k;i++){
            res=Math.max(res,dp[i][0]);
        }
        return res;
    }
}