面試時(shí)遇到股票買賣問題（k次交易），因?yàn)橹罢莆詹皇鞗]做出來打擊還是挺大的，于是狂刷這類問題，對動態(tài)規(guī)劃，特別是畫狀態(tài)轉(zhuǎn)換圖，并根據(jù)圖寫狀態(tài)轉(zhuǎn)移方程了解的更加深入。

買賣股票的最佳時(shí)機(jī)

如果你最多只允許完成一筆交易（即買入和賣出一支股票一次），設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。

買賣股票的最佳時(shí)機(jī) II

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

買賣股票的最佳時(shí)機(jī) III

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你最多可以完成兩筆交易。

買賣股票的最佳時(shí)機(jī) IV

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你最多可以完成k 筆交易。

最佳買賣股票時(shí)機(jī)含冷凍期

設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)

你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購買了一個(gè)股票，在賣出它之前你就不能再繼續(xù)購買股票了。

股票買賣問題的狀態(tài)轉(zhuǎn)移圖如圖所示，有兩個(gè)狀態(tài)分別代表買入和賣出股票后，同時(shí)也可選擇持有不進(jìn)行狀態(tài)轉(zhuǎn)移操作。

使用dp[i][k][0]和dp[i][k][1]表示狀態(tài)，其中dp[i][k][0]表示第i天最多進(jìn)行k次交易時(shí)賣出后的利潤，dp[i][k][1]表示第i天最多進(jìn)行k次交易時(shí)買入后的利潤。

初始條件

dp[i][0][0] = 0 #沒有進(jìn)行任何買入，當(dāng)前持有利潤為0
dp[i][0][1] = -prices[0] #進(jìn)行一次賣出，當(dāng)前利潤為 -prices[0]

根據(jù)狀態(tài)轉(zhuǎn)移圖，可寫出動態(tài)轉(zhuǎn)移方程

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[I]) 
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[I])

特別地，當(dāng)k=1時(shí)(買賣股票的最佳時(shí)機(jī))，dp[i-1][k-1][0] === 0，故可簡化為

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[I])
dp[i][1] = max(dp[i-1][1],  - prices[I])

當(dāng)k=float('inf')時(shí)(買賣股票的最佳時(shí)機(jī) II)，k=k-1，故可簡化為

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[I])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[I])

下面兩道題是在k無限次時(shí)增加條件，因此對上述方程進(jìn)行修改。

含冷凍期問題(最佳買賣股票時(shí)機(jī)含冷凍期)因?yàn)樵黾恿?天的冷凍時(shí)間，在賣出后（狀態(tài)1）無法在第二天進(jìn)行買入（買入），因此買入時(shí)非i-1天而是i-2天，狀態(tài)轉(zhuǎn)移方程為：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[I])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[I])

含手續(xù)費(fèi)問題(買賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi))的狀態(tài)轉(zhuǎn)移方程。

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[I])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)

當(dāng)k=2時(shí)(買賣股票的最佳時(shí)機(jī) III)，可使用一般形式的狀態(tài)轉(zhuǎn)移方程解決。

一般情況下（買賣股票的最佳時(shí)機(jī) IV）的完整代碼如下：

class Solution:
def maxProfit(self,k: int, prices: List[int]) -> int:

    if not prices:
        return 0

    dp = [[[0] * 2  for _ in range(k+1) ]for _ in range(len(prices))]

    for k in range(1,k+1):
        dp[0][k][0] = 0
        dp[0][k][1] = -prices[0]

    for i in range(1,len(prices)):
        for k in range(1,k+1):
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[I])
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[I])
    
    return dp[-1][k][0]

在本題測試用例中有一個(gè)較大的k導(dǎo)致程序超時(shí)，當(dāng)k較大時(shí)（k > len(prices)//2），此時(shí)說明每天都在買入或賣出操作，用貪心算法將這一特殊情況處理掉。

    if k > len(prices)//2:
        maxnum = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                maxnum += prices[i] - prices[i-1]
        return maxnum