九十三、動態(tài)規(guī)劃系列之股票問題（下）

「@Author：Runsen」

動態(tài)規(guī)劃必須要面對股票系列，背包系列差不多了，那就上吧。

股票買賣這一類的問題，都是給一個輸入數(shù)組，里面的每個元素表示的是每天的股價，并且你只能持有一支股票（也就是你必須在再次購買前出售掉之前的股票），一般來說有下面幾種問法：

• 只能買賣一次
• 只能買賣兩次
• 可以買賣無數(shù)次
• 可以買賣 k 次
• 買 N 次加 CD 冷卻時間
• 買 N 次加手續(xù)費

需要你設(shè)計一個算法去獲取最大的利潤。

買賣股票的最佳時機（買N次加CD冷卻時間）

這是Leetcode的第309題： 買賣股票的最佳時機（買N次加CD冷卻時間）

給定一個整數(shù)數(shù)組，其中第 i 個元素代表了第 i 天的股票價格 。

你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。示例:

輸入: [1,2,3,0,2]
輸出: 3 
解釋: 對應的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]

此題的關(guān)鍵是如何設(shè)置dp的狀態(tài)？冷凍期其實就是CD技能的時間。

dp[i][0]表示第i天結(jié)束之后，我有股票的最大收益。那么有可能i-1天我本來就有股票，今天的價不好，我不賣了，或者昨天我沒有股票，但我今天可以買了股票，說明今天不是冷凍期。

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

dp[i][1]表示第i天結(jié)束之后，我沒有股票，明天就是冷凍期，也就是昨天有股票，今天運氣好，價格高，我剛剛賣了股票這一種可能。

dp[i][1] = dp[i-1][0] + prices[i]

dp[i][2]表示第i天結(jié)束之后，我沒有股票，但是明天不在冷凍期，也就是今天我不買股票，有可能因為我昨天剛剛賣了，今天就是冷凍期，我買不了。也有可能，昨天的我可能沒打算買，今天又不買。

dp[i][2] = max(dp[i-1][1] ,dp[i-1][2])

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
       
        if not prices: return 0
        n = len(prices)
        # 第0天dp[0][0]要買是第一個股
        dp = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)]
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
            dp[i][1] = dp[i-1][0] + prices[i]
            dp[i][2] = max(dp[i-1][1] ,dp[i-1][2])
        return max(dp[-1][1], dp[-1][2])

在可以買賣無數(shù)次中，最好的做法就是有一個變量儲存沒有股票的最大利潤和有股票的最大利潤，然后不斷地維護。

當然此題，也可以采用這種的思想，分兩種狀態(tài)buy和sell

• 最后一次操作是購買的情況下，前i天的最大獲利為buy[i]
• 最后一次操作是售出的情況下，前i天的最大獲利為sell[i]

狀態(tài)轉(zhuǎn)移如下：

要求最后一次為購買的前i天最大獲利buy[i]，分兩種情況：

第i天購買，則在i-2天之前已售出，需要找出前i-2天最后一次是售出的最大獲利sell[i-2]，再減去購買當日的價格price[i]。

不購買，與前一天獲利相同，即buy[i-1]， 因此buy[i] = max(sell[i-2] - price[i], buy[i-1])

同理，根據(jù)最后一天是否出售，可以將sell[i]的求取分兩種情況，去最大值，即sell[i] = max(buy[i-1]+price[i], sell[i-1])

最后求得sell[n]即為所求。

class Solution(object):
    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0
        sell = [0] * len(prices)
        buy = [-prices[0]] * len(prices)
        for i in range(1, len(prices)):
            buy[i] = max(buy[i-1], sell[i-2] - prices[i])
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
        return sell[len(prices)-1]

買賣股票的最佳時機（買N次加手續(xù)費）

這是Leetcode的第714題： 買賣股票的最佳時機（買N次加手續(xù)費）

給定一個整數(shù)數(shù)組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負整數(shù) fee 代表了交易股票的手續(xù)費用。

注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費。

輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達到的最大利潤:  
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

此題就是在dp[i][0]減去手續(xù)費而已，本題只需要在計算賣出操作的時候減去手續(xù)費就可以了，代碼幾乎是一樣的。

注釋寫得很詳細了。

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

在可以買賣無數(shù)次中，使用有一個變量儲存沒有股票的最大利潤和有股票的最大利潤，只要在賣出的時候減去手續(xù)費即可。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # cash表示第i天結(jié)束，沒有股票的最大利潤
        # hold表示第i天結(jié)束，有股票的最大利潤
        cash, hold = 0, -prices[0]
        for i in range(1,len(prices)):
            cash = max(cash,hold+prices[i]-fee)
            hold = max(hold,.cash-prices[i])
        return cash