参考：买卖股票的最佳时机【基础算法精讲 21】_哔哩哔哩_bilibili
ps：笔记中的代码按本人理解整理，重思路，非原视频中的代码，也并非最优代码
题目1：买卖股票的最佳时机 II（不限交易次数）
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
- 思路：第n天结束时的利润 = 第n-1天结束时的利润 + 第n天的利润
- 状态：持有 & 未持有
- 持有 ---> 未持有 （卖）：金额增加当日股价 （+ price）
- 未持有 --> 持有 （买）：金额减少当日股（- price）
- 使用二维DP储存每日金额（持有状态*天数）
- 代码
-
class Solution: def maxProfit(self, prices: List[int]) -> int: dp = [[0]*2 for _ in range(len(prices)+1)] # dp[0]表示未持有， dp[1]表示持有 dp[0][0] = 0 dp[0][1] = -float('inf') for i in range(1, len(dp)): # price为i-1，因为遍历时i从1开始 dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1]) dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i-1]) return dp[-1][0]
-
题目2: 买卖股票的最佳时机（一次交易）
- 变化： 只能有一次交易
- 状态：持有 & 未持有 （只需要 持有 ➡️ 未持有 的一次转化）
- 持有（负数）：买股票之后的最大值（ - price1 的最大值）
- 未持有：卖了股票之后的最大值（price2 - price1)
- 代码（变化部分）
-
dp[i][1] = max(dp[i-1][1], -prices[i-1]) dp[i][0] = max(dp[i-1][0], dp[i][1]+prices[i-1])
-
题目3: 最佳买卖股票时机含冷冻期（间隔交易）
- 变化： 卖了之后必须隔 >=1 天才能买
- 状态：持有 & 未持有
- 持有【第n-1天】 ---> 未持有【第n天】（卖）：金额增加当日股价 （+ price）
- 未持有 【第n-2天】 --> 持有 【第n天】（买）：金额减少当日股（- price）
- 代码（变化部分）
-
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1]) dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i-1])
-
题目4: 买卖股票的最佳时机 IV（最多 k 次交易）
- 变化：最多完成 k 次交易【增加一个维表示次数】
- 状态：持有 & 未持有
- 持有 ---> 未持有 （卖）：金额增加当日股价 （+ price），并且剩余可交易次数 -1
- 未持有 --> 持有 （买）：金额减少当日股（- price）
- 代码
-
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: # k+2 是因为要确定边界条件 dp = [[[-float('inf')]*2 for _ in range(k+2)]for _ in range(len(prices)+1)] # 初始状态 k+1 对应的dp[0][k+1][:] 还是用 -float('inf') 界定 for j in range(k+1): dp[0][j][0] = 0 for i in range(1, len(dp)): for j in range(k, -1, -1): # dp[i][k][1] 不会由 dp[i][k+1][0]=-float('inf') 转移而来 # 所以第一次交易是从 dp[i][k][1] 转移到 dp[i][k-1][0] 开始的 # 如果完成所有k次交易，则实现 dp[i][1][1] 到 dp[i][0][0] dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j+1][1]+prices[i-1]) dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]-prices[i-1]) return dp[-1][0][0]
-