九十二、動(dòng)態(tài)規(guī)劃系列之股票問(wèn)題（上）

「@Author：Runsen」

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

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

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

需要你設(shè)計(jì)一個(gè)算法去獲取最大的利潤(rùn)。

買賣股票的最佳時(shí)機(jī)（買一次）

這是 Leetcode 的第 121 題： 買賣股票的最佳時(shí)機(jī)（買一次）

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出，最大利潤(rùn) = 6-1 = 5 。
     注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買入價(jià)格。

思路

示例：[7,1,5,3,6,4]
(1) i = 0，min = 7，result = 0；
(2) i = 1，min = 1，result = 0；
(3) i = 2，min = 1，result = 5 - 1 = 4；
(4) i = 3，min = 1，result = 4；
(5) i = 4，min = 1，result = 6 - 1 = 5；
(6) i = 5，min = 1，result = 5；

首先，定義 dp[i] 的含義為：第 i 天的最大利潤(rùn)。

一次買賣股票得到最大利潤(rùn)的當(dāng)然是歷史最低點(diǎn)買，因此思路為：遍歷一遍數(shù)組，計(jì)算每次到當(dāng)天為止的最小股票價(jià)格和最大利潤(rùn)。

因此狀態(tài)轉(zhuǎn)移方程：比較前一天的利潤(rùn)和今天的賣出減去最小的股票價(jià)格。

然后問(wèn)題轉(zhuǎn)移到了求minprice歷史最低點(diǎn)，因此轉(zhuǎn)化為求滑動(dòng)數(shù)組的最小值的問(wèn)題，方法就是假設(shè)第一個(gè)為最小值，不斷地比較替換。

邊界問(wèn)題：dp = [0] * n

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp的狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-1],prices[i]-minprice)
        n = len(prices)
        if n == 0: return 0
        dp = [0] * n
        minprice = prices[0]
        for i in range(1,n):
            minprice = min(minprice,prices[i])
            dp[i] = max(dp[i-1],prices[i]-minprice)
        return dp[-1]

買賣股票的最佳時(shí)機(jī)（買 N 次）

這是 Leetcode 的第 122 題： 買賣股票的最佳時(shí)機(jī)（買 N 次）

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
     隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 。
你只能

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

由于可以買賣多次，那么 dp 就需要開(kāi)一個(gè)維度來(lái)表示當(dāng)天是買還是賣，因此是動(dòng)態(tài)規(guī)劃二維數(shù)組 dp。

dp[i][0] 表示前 i 天的最大利潤(rùn)，第 i 天不買，那么 dp 轉(zhuǎn)移方程取決于 i-1 天是有股票還是沒(méi)有股票。

dp[i][1] 表示前 i 天的最大利潤(rùn)，第 i 天必須買, 那么 dp 轉(zhuǎn)移方程取決于 i-1 天是有股票還是沒(méi)有股票

最后，第 i 天不可以買股票。當(dāng)然是dp[i][0] 比dp[i][1]大

對(duì)此，還有貪心的做法，找到所有的上升區(qū)間，計(jì)算每個(gè)上升區(qū)間的價(jià)格差,直接節(jié)約了空間復(fù)雜度為 O(1)，也就是，只有明天比我今天的開(kāi)的高，我就賣。

還可以對(duì)第一種常規(guī)方法進(jìn)行空間優(yōu)化，因此我們不需要第i-1天的最大利潤(rùn)。我們只需要使用兩個(gè)變量?jī)?chǔ)存第i天沒(méi)有股票的最大利潤(rùn)和有股票的最大利潤(rùn)，然后不斷地維護(hù)更新。

class Solution:
    def maxProfit(self, prices: List[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])
            dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])
        return dp[-1][0]

        # 貪心做法
        n = len(prices)
        profit = 0
        if n == 0 : return 0
        for i in range(1,n):
            if prices[i] > prices[i-1]:
                profit += prices[i] - prices[i-1]
        return profit

  # 最好的做法就是有一個(gè)變量?jī)?chǔ)存沒(méi)有股票的最大利潤(rùn)和有股票的最大利潤(rùn)，然后不斷地維護(hù)
  # cash表示第i天結(jié)束，沒(méi)有股票的最大利潤(rùn)
        # hold表示第i天結(jié)束，有股票的最大利潤(rùn)
        cash, hold = 0, -prices[0]
        for i in range(1,len(prices)):
            cash = max(cash,hold+prices[i])
            hold = max(hold,cash-prices[i])
        return cash

買賣股票的最佳時(shí)機(jī)（買 2 次）

這是 Leetcode 的第 123 題：買賣股票的最佳時(shí)機(jī)（買 2 次）

輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價(jià)格 = 0）的時(shí)候買入，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 3-0 = 3 。
     隨后，在第 7 天（股票價(jià)格 = 1）的時(shí)候買入，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 4-1 = 3 。

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

注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

與第二個(gè)不同在于，第二題你可以買無(wú)數(shù)次，但是現(xiàn)在只給你買 2 次。

我們直接把 2 次變成 K 次，變成第四題。因此變成了動(dòng)態(tài)規(guī)劃三維 dp 數(shù)組，多用一個(gè)維度定義了次數(shù)。

所以定義狀態(tài)轉(zhuǎn)移數(shù)組dp[天數(shù)][賣出的次數(shù)][當(dāng)前是否持股]

狀態(tài)的dp[i][k][XX]定義就是：i 表示第i天的最大利潤(rùn)，k表示第i天之前你買賣的次數(shù)，X 表示第i天是否有股票 0 ，1。在這里的 K 是 2。

具體一天結(jié)束時(shí)的 5 種狀態(tài)：

• 未持股，未賣出過(guò)股票：說(shuō)明從未進(jìn)行過(guò)買賣，利潤(rùn)為 0。dp[i][0][0]=0

• 未持股，賣出過(guò) 1 次股票：可能是昨天有股票，今天賣出，也可能昨天也未持股，但是之前賣出過(guò)。dp[i][1][0]=max(dp[i-1][0][1]+prices[i],dp[i-1][1][0])

• 未持股，賣出過(guò) 2 次股票:可能是昨天有股票，今天賣出，昨天還賣出過(guò) 1 次股票，也可能是昨天也未持股，但是之前賣出過(guò) 2 次。dp[i][2][0]=max(dp[i-1][1][1]+prices[i],dp[i-1][2][0])

• 持股，未賣出過(guò)股票：可能昨天沒(méi)有買股票，就是今天買的，也可能是之前買的，昨天就持股，所有今天也持股。dp[i][0][1]=max(dp[i-1][0][0]-prices[i],dp[i-1][0][1])

• 持股，賣出過(guò) 1 次股票：可能是今天買的，但是在昨天之前賣出過(guò) 1 次股票，也可能是之前買了股票，也賣出過(guò) 1 次股票，昨天是持股狀態(tài)。dp[i][1][1]=max(dp[i-1][1][0]-prices[i],dp[i-1][1][1])

加上之前的狀態(tài)轉(zhuǎn)移方程：

第 i 天（未持股），狀態(tài)轉(zhuǎn)移方程就是昨天未持股的最大利潤(rùn)，和昨天持股的最大利潤(rùn)加上今天賣出。

第 i 天（持股），狀態(tài)轉(zhuǎn)移方程就是昨天持股的最大利潤(rùn)，和昨天未持股的最大利潤(rùn)加上今天買入。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n = len(prices)
        # 初始化狀態(tài)
        dp = [[[0]*2 for _ in range(3)] for _ in range(n)]
        for k in range(3):
         # 第一天買入股票
            dp[0][k][1] = -prices[0]
        # 從 i=1 處開(kāi)始迭代
        for i in range(1, n):
            for k in range(1, 3):
                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][2][0]

因此畢竟是買賣 2 次，在第二次買的時(shí)候，用第一次的掙到的錢抵消了一部分第二次買的錢

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1, n):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1 + prices[i])
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, buy2 + prices[i])
        rbueturn sell2

買賣股票的最佳時(shí)機(jī)（買 k 次）

這是 Leetcode 的第 188 題： 買賣股票的最佳時(shí)機(jī)（買 k 次）

輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價(jià)格 = 2) 的時(shí)候買入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-2 = 4 。
     隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 3-0 = 3 。

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

這道題理論上和 LeetCode 123（交易次數(shù)最多為 2） 的解法一樣，但是直接提交容易出現(xiàn)超內(nèi)存的錯(cuò)誤，是測(cè)試用例提供的 K 太大導(dǎo)致的。

因此,需要對(duì) K 進(jìn)行處理，有效的交易由買入和賣出構(gòu)成，至少需要兩天；反之，當(dāng)天買入當(dāng)天賣出則視為一次無(wú)效交易。因此 K 必須小于n//2 。

如果題目給定的最大交易次數(shù) k<=n//2，這個(gè) k 是可以有效約束交易次數(shù)的，本題為 LeetCode 123（交易次數(shù)為2次）；如果給定的 k>n//2 ，本題為 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:
        if k == 0 or len(prices) < 2:
           return 0
        n = len(prices)
        res = []
        # 如果k的次數(shù)大于n//2，那么就是直接計(jì)算利潤(rùn)，第一天買，第二天就賣，然后第二天在買。
        if k > n // 2:
            # 下面就是Leetcode第122的代碼 
            max_profit = 0
            for i in range(1,n):
                profit = prices[i] - prices[i - 1]
                # 如果第二天比第一天高，那就直接加入
                if profit > 0:
                    max_profit += profit
            return max_profit
        # 下面就是Leetcode第123的代碼 
        dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]
        for i in range(k + 1):
            # 第一天買入股票
            dp[0][i][1] = - prices[0]
        for i in range(1, n):
            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])
        # 求dp[i][k][0] 的最大，這里直接開(kāi)數(shù)組 , 比較每一個(gè)次數(shù)的最大利潤(rùn)
        for m in range(k + 1):
            res.append(dp[-1][m][0])
        return max(res)