算法D50 | 动态规划11 | 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

视频讲解：动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III_哔哩哔哩_bilibili

代码随想录

Python:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0]*4 for _ in range(n)]
        dp[0][0] = -prices[0]
        dp[0][2] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], -prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i])
            dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i])
        return dp[n-1][3]

C++:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
        dp[0][0] = -prices[0];
        dp[0][2] = -prices[0];
        for (int i=1; i<prices.size(); i++) {
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i]);
        }
        return dp[prices.size()-1][3];
    }
};

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

本题是123.买卖股票的最佳时机III 的进阶版  

视频讲解：动态规划来决定最佳时机，至多可以买卖K次！| LeetCode：188.买卖股票最佳时机4_哔哩哔哩_bilibili

代码随想录

Python:

123的扩展版，这个版本记账型递推公式的优势就显示出来了。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0]*(k*2+1) for _ in range(n)]
        for j in range(k):
            dp[0][j*2+1] = -prices[0]
        for i in range(1, n):
            for j in range(1,k*2+1):
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+(-1)**j*prices[i])
        return dp[-1][-1]

C++:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(k*2+1, 0));
        for (int i=0; i<k; i++) {
            dp[0][i*2+1] = -prices[0];
        }
        for (int i=1; i<prices.size(); i++) {
            for (int j=0; j<k*2-1; j+=2) {
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
                dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);
            }
        }
        return dp[prices.size()-1][2*k];
    }
};