在 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] = 0dp[0][1][1] = -prices[0]dp[0][2][0] = 0dp[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 0n = 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] = 0dp[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] = 0dp[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]

總結

以上是生活随笔為你收集整理的买卖股票类问题动态规划解法（Leetcode题解-Python语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。