代码随想录训练营二刷第五十二天 | 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

代码随想录训练营二刷第五十二天 | 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

一、123.买卖股票的最佳时机III

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
思路：这次限定只能买卖两次，故定义每天有四种状态。
dp[0]表示第i天第一次持有手中金额的最大值。
dp[1]表示第i天第一次不持有手中金额的最大值。
dp[2]表示第i天第二次持有手中金额的最大值。
dp[3]表示第i天第二次不持有手中金额的最大值。
持有意思是可以是今天才持有，也可以是之前持有的。
不持有意思是可以是今天才不持有的，也可以是之前就已经不持有了。
于是有下面的4个递推公式，此外要注意dp数组的初始化，初始化时要把4种情况都初始化了，严格按照定义来。

class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[4];
        dp[0] = -prices[0];
        dp[2] = -prices[0];
        for(int i = 1; i < prices.length; i++) {
        	dp[0] = Math.max(dp[0], -prices[i]);
        	dp[1] = Math.max(dp[1], dp[0]+prices[i]);
        	dp[2] = Math.max(dp[2], dp[1]-prices[i]);
        	dp[3] = Math.max(dp[3], dp[2]+prices[i]);
        }
        return dp[3];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
思路：思路和上一题基本一致，上一题是只能买卖两次，本题无非是可以买卖k次，这样每一天都有2k种状态，除了第一次没有前置的值，后面都一样，里面写了一个for循环并不是嵌套，而是k次没有一个具体的数，没法展开写，就只能这样，可以说搞定了这题不管是可以买几次都没问题。

class Solution {
     public int maxProfit(int k, int[] prices) {
        int[] dp = new int[2*k];
        for (int i = 0; i < dp.length; i++) {
            if (i % 2 == 0) {
                dp[i] = -prices[0];
            }
        }
        for (int i = 1; i < prices.length; i++) {
            dp[0] = Math.max(dp[0], -prices[i]);
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
            // 以下是2，3,4,5一直到2*k的计算，不再展开写了，直接for循环
            for (int j = 2; j < 2*k; j += 2) {
                dp[j] = Math.max(dp[j], dp[j-1] - prices[i]);
                dp[j+1] = Math.max(dp[j+1], dp[j] + prices[i]);
            }
        }
        return dp[dp.length-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20