九十三、动态规划系列之股票问题（下）

「@Author：Runsen」

动态规划必须要面对股票系列，背包系列差不多了，那就上吧。

股票买卖这一类的问题，都是给一个输入数组，里面的每个元素表示的是每天的股价，并且你只能持有一支股票（也就是你必须在再次购买前出售掉之前的股票），一般来说有下面几种问法：

• 只能买卖一次
• 只能买卖两次
• 可以买卖无数次
• 可以买卖 k 次
• 买 N 次加 CD 冷却时间
• 买 N 次加手续费

需要你设计一个算法去获取最大的利润。

买卖股票的最佳时机（买N次加CD冷却时间）

这是Leetcode的第309题： 买卖股票的最佳时机（买N次加CD冷却时间）

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

此题的关键是如何设置dp的状态？冷冻期其实就是CD技能的时间。

dp[i][0]表示第i天结束之后，我有股票的最大收益。那么有可能i-1天我本来就有股票，今天的价不好，我不卖了，或者昨天我没有股票，但我今天可以买了股票，说明今天不是冷冻期。

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

dp[i][1]表示第i天结束之后，我没有股票，明天就是冷冻期，也就是昨天有股票，今天运气好，价格高，我刚刚卖了股票这一种可能。

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

dp[i][2]表示第i天结束之后，我没有股票，但是明天不在冷冻期，也就是今天我不买股票，有可能因为我昨天刚刚卖了，今天就是冷冻期，我买不了。也有可能，昨天的我可能没打算买，今天又不买。

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])

在可以买卖无数次中，最好的做法就是有一个变量储存没有股票的最大利润和有股票的最大利润，然后不断地维护。

当然此题，也可以采用这种的思想，分两种状态buy和sell

• 最后一次操作是购买的情况下，前i天的最大获利为buy[i]
• 最后一次操作是售出的情况下，前i天的最大获利为sell[i]

状态转移如下：

要求最后一次为购买的前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])

同理，根据最后一天是否出售，可以将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次加手续费）

这是Leetcode的第714题： 买卖股票的最佳时机（买N次加手续费）

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

输入: 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]减去手续费而已，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。

注释写得很详细了。

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]

在可以买卖无数次中，使用有一个变量储存没有股票的最大利润和有股票的最大利润，只要在卖出的时候减去手续费即可。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # cash表示第i天结束，没有股票的最大利润
        # hold表示第i天结束，有股票的最大利润
        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