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

教程视频：https://www.bilibili.com/video/BV1rP4y1D7ku

解法一：动态规划

思路：
1、dp[i][j]含义： 第 i 天 j 状态下手中所持金额。j 共有状态：0表示未持有股票且不在冷冻期，1表示持有股票，2表示冷冻期。
2、递推公式：
dp[i][0]=Math.max(dp[i-1][0], dp[i-1][2]);
dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
dp[i][2]=dp[i-1][1]+prices[i];
3、初始化dp：
dp[0][0]=0;
dp[0][1]=-prices[0];
dp[0][2]=0;
4、遍历顺序：正向遍历
5、打印验证

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][3];

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

        for(int i=1;i<prices.length;i++){
            dp[i][0]=Math.max(dp[i-1][0], dp[i-1][2]);
            dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
            dp[i][2]=dp[i-1][1]+prices[i];
        }
        return Math.max(dp[prices.length-1][0], dp[prices.length-1][2]);
    }
}

714.买卖股票的最佳时机含手续费

教程视频：https://www.bilibili.com/video/BV1z44y1Z7UR

解法一：动态规划

思路：
1、dp[i][j]含义：第 i 天 j 状态下手中所持金额。j 共有状态：0表示未持有股票，1表示持有股票。
2、递推公式：
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][0]-prices[i]-fee);//买入时支付费用
3、初始化dp：dp[0][0]=0;
dp[0][1]=-prices[0]-fee;
4、遍历顺序：正向遍历；
5、打印验证

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][1]=-prices[0]-fee;
        for(int i=1;i<prices.length;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][0]-prices[i]-fee);
        }
        return dp[prices.length-1][0];
    }
}

//空间优化
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[] dp = new int[2];
        dp[1]=-prices[0]-fee;
        for(int i=1;i<prices.length;i++){
            dp[0]=Math.max(dp[0], dp[1]+prices[i]);
            dp[1]=Math.max(dp[1], dp[0]-prices[i]-fee);
        }
        return dp[0];
    }
}

股票问题总结

一共做了6道股票题目：

121. 买卖股票的最佳时机，122.买卖股票的最佳时机II

123.买卖股票的最佳时机III，188.买卖股票的最佳时机IV

309. 最佳买卖股票时机含冷冻期，714.买卖股票的最佳时机含手续费

1. 121.买卖股票的最佳时机只能买卖一次
2. 122.买卖股票的最佳时机II可以买卖多次
3. 123.买卖股票的最佳时机III至多可以买卖两次
4. 188.买卖股票的最佳时机IV至多可以买卖k次
5. 309.最佳买卖股票时机含冷冻期冷冻期不能买卖
6. 714.买卖股票的最佳时机含手续费可以买卖多次但每次交易需要支付手续费

第1，2题的差异在于第 i 天买入股票时，1题手中金额为0，二题手中金额为上一阶段未持有时金额dp[i-1][0]。
第3，4题将状态增加了，尤其是第四题，需要2*k列来描述第 i 天的状态，其余和第二题差异不大。
第5题增加了一个冷冻期状态，其递推转移相较于第2题有变化。
第6题相较于第2题仅在买入或者卖出时扣除手续费即可