动态规划part09｜188.买卖股票的最佳时机IV 、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、股票问题总结

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

• 🔗：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
• 思路：（参考了灵茶山艾府的视频）把最多交易2次升级为最多交易k次，此题可以用状态机的思路考量
  • 对于第i天，可以持有股票或者不持有股票，且交易的次数为j次
  • 买入和卖出视为完成一次交易，由于最后未持有股票，手上的股票一定会卖掉，所以代码中的j-1可以写在买股票的时候，也可以写在卖股票的时候，这两种写法都是可以的。
  • 
• 代码：

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n =prices.length;
        int[][][] f = new int [n+1][k+2][2];
        // initialize
        for(int[][] mat:f){
            for(int[] row : mat){
                Arrays.fill(row, Integer.MIN_VALUE / 2); // prevent from overflow
            }
        }
        for(int j=1; j<=k+1; j++){
            f[0][j][0] = 0;
        }
        // dp process
        for(int i=0; i<n; i++){
            for(int j=1; j<=k+1; j++){
            f[i+1][j][0] = Math.max(f[i][j][0],f[i][j-1][1]+prices[i]);
            f[i+1][j][1] = Math.max(f[i][j][1], f[i][j][0]-prices[i]);
            }
        }
        return f[n][k+1][0];
    }
}

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

• 🔗：309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
• 思路：这一题其实和打家劫舍很像，都是需要至少隔一天再进行交易，其实就是在原有的基础上进行改动。之前买入的时候考虑的是第i-1天，现在考虑第i-2天的profit
• 代码：

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

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

• 🔗：714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
• 思路：和188题（今天的第一题）没有什么区别
• 代码：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] f = new int[n+1][2];
        f[0][0] = 0;
        f[0][1] = Integer.MIN_VALUE/2;
        for(int i=0; i<n; i++){
            f[i+1][0] = Math.max(prices[i]-fee+f[i][1], f[i][0]);
            f[i+1][1] = Math.max(f[i][0]-prices[i], f[i][1]);
        }
        return f[n][0];
    }
}