买卖股票类问题动态规划解法（Leetcode题解-Python语言）

买卖股票类问题动态规划解法（Leetcode题解-Python语言）

在 Leetcode 中，关于买卖股票的问题共有6道，而这些题目是可以用相同的思维进行求解的，强烈推荐这篇总结，写得非常到位。

股票类问题的动态规划分三步走，1、首先明确方程的含义，

T[i][k][0]：表示在第 i 天结束时，最多进行 k 次交易且在进行 *** 作后持有 0 份股票的情况下可以获得的最大收益；
T[i][k][1]：表示在第 i 天结束时，最多进行 k 次交易且在进行 *** 作后持有 1 份股票的情况下可以获得的最大收益。

2、初始（基准）情况：

T[-1][k][0] = 0, T[-1][k][1] = -Infinity
T[i][0][0] = 0, T[i][0][1] = -Infinity

T[-1][k][0] = 0：交易开始前没有股票，收益为0；
T[-1][k][1] = -Infinity：交易开始前有股票，这是不可能的，为负收益；
T[i][0][0] = 0：交易开始了，不允许买股票也不持有股票，收益为0；
T[i][0][1] = -Infinity：交易开始了，不允许买股票但是持有股票，这是不可能的，收益为0。

3、状态转移方程：

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

第一行：第 i 天没有股票的最大收益，是上一天也没有股票（挂机）的收益和上一天有股票然后今天卖掉的收益，两者中最大的。
第二行：第 i 天持有股票的最大收益，是上一天也持有股票（挂机）的收益和上一天没有股票然后今天买了股票的收益，两者中最大的。注意允许交易的次数 k 在买入时减去1。

121. 买卖股票的最佳时机（剑指 Offer 63. 股票的最大利润）

只能买卖一次股票，k = 1，状态转移方程为：

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

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        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][1], -prices[i])

        return dp[n - 1][0]

122. 买卖股票的最佳时机 II

可以无限次买卖股票，k 为正无穷，状态转移方程为：

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

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

        return dp[n - 1][0]

123. 买卖股票的最佳时机 III

最多买卖两次股票，k = 2，状态转移方程为：

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

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

        for i in range(1, n):
            dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
            dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
            dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
            dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])

        return dp[n - 1][2][0]

188. 买卖股票的最佳时机 IV

k 为给定的任意值，买卖要两天时间，天数 n 是有限的，所以实际上的 k 为 min(k, n // 2)。

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

        n = len(prices)
        k = min(k, n // 2)
        dp = [[[0] * 2 for _ in range(k+1)] for _ in range(n)]
        for i in range(1, k+1):
            dp[0][i][0] = 0
            dp[0][i][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[n - 1][k][0]

309. 最佳买卖股票时机含冷冻期

k 实际上为正无穷，但是有冷冻期，如果要在第 i 天买入股票，第二个状态转移方程中就不能使用 T[i - 1][k][0]，而应该使用 T[i - 2][k][0]，状态转移方程为：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
T[i][k][1] = max(T[i - 1][k][1], T[i - 2][k][0] - prices[i])

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

        return dp[n - 1][0]

714. 买卖股票的最佳时机含手续费

k 实际上为正无穷，但是有手续费，在买入（第一条方程）和卖出（第二条方程）中减去手续费都是可以的，在买入时减去手续费的状态转移方程为：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i])
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k][0] - prices[i] - fee)

在卖出时减去手续费的状态转移方程为：

T[i][k][0] = max(T[i - 1][k][0], T[i - 1][k][1] + prices[i] - fee)
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k][0] - prices[i])

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

        return dp[n - 1][0]