題目

這道題理論上和 LeetCode 123（交易次數(shù)最多為2） 的解法一樣，動(dòng)態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移方程：

dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i]) # 右邊:今天賣(mài)了昨天持有的股票，所以?xún)商熨I(mǎi)入股票的次數(shù)都是j
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i]) # 右邊:昨天沒(méi)有持股而今天買(mǎi)入一只，故昨天買(mǎi)入的次數(shù)是j-1

但是直接提交容易出現(xiàn)超內(nèi)存的錯(cuò)誤，是 DP Table 太大導(dǎo)致的。

有效的交易由買(mǎi)入和賣(mài)出構(gòu)成，至少需要兩天；反之，當(dāng)天買(mǎi)入當(dāng)天賣(mài)出則視為一次無(wú)效交易。如果題目給定的最大交易次數(shù) k<=n/2，這個(gè) k 是可以有效約束交易次數(shù)的；如果給定的 k>n/2 ，那這個(gè) k 實(shí)際上起不到約束作用了，可以認(rèn)為 k=+inf，本題退化為 LeetCode 122（不限交易次數(shù)） 。

題目整體思路是判斷 k 和 n/2 的大小關(guān)系，兩個(gè)分支分別用 LeetCode 123 和 LeetCode 122 的代碼解決，可有效防止內(nèi)存超出。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1: return 0

        if k >= n//2:   # 退化為不限制交易次數(shù)
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]
            return profit

        else:           # 限制交易次數(shù)為k
            dp = [[[None, None] for _ in range(k+1)] for _ in range(n)]  # (n, k+1, 2)
            for i in range(n):
                dp[i][0][0] = 0
                dp[i][0][1] = -float('inf')
            for j in range(1, k+1):
                dp[0][j][0] = 0
                dp[0][j][1] = -prices[0]
            for i in range(1, n):
                for j in range(1, k+1):
                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
            return dp[-1][-1][0]