经典问题
简述：存在股票的价格数组，只能选择某一天买入的股票，并在未来某一个不同的日子卖出，计算最大利润。
输入：[7, 1, 5, 3, 6, 4] 输出：5 = 6 - 1 输入：[7, 6, 4, 3, 1] 输出：0 无买入卖出 # 买卖股票的最佳时机I def max_profit_1(prices): l = len(prices) if len == 0: return 0 dp = [[0] * 2 for _ in range(l)] dp[0][0] = -prices[0] dp[0][1] = 0 for i in range(1, l): dp[i][0] = max(dp[i - 1][0], -prices[i]) dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]) return dp[-1][1]
思路
关键思路在于：”买入卖出“ >> “持有不持有”，因为dp记录状态的时候，“持有不持有”才是一种持续的状态，即额外记录状态即可
动态规划五部曲分析：
1、确定dp数组以及下标的含义
dp[i][0]表示第i天持有股票的最多现金；dp[i][1]表示第i天不持有股票的最多现金；买入时扣除花费金额
2、确定递推公式
- 第i天持有股票dp[i][0]可由以下两者状态所致
- 第i-1天就已经持有，保持现状，即dp[i-1][0]
- 第i天买入，即-price[i]（股票价格）
- 即dp[i][0] = max(dp[i-1][0], -price[0])
- 第i天不持有股票dp[i][1]可由两者状态所致
- 第i-1天就已经不持有，保持现状，即dp[i-1][1]
- 第i天卖出了股票，即dp[i-1][0] + price[i]
- 即dp[i][1] = max(dp[i-1][1], dp[i-1][0]+price[i])
3、dp数组如何初始化
基础在于dp[0][0]和dp[0][1]，即dp[0][0]=-price[0]，dp[0][1]=0
4、确定遍历顺序，即从前向后
5、举例推导dp数组
注：链接中图解更方便理解
拓展题型
股票买卖的最佳时机II
约束条件：可以多次交易，但不准同时持有多支股票
解题思路：递归公式的改变
- 即dp[i][0] = max(dp[i-1][0], dp[i-1][1]-price[i])
# 买卖股票的最佳时机II def max_profit_2(prices): # 同上相似，只需修改dp[i][0] # dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) return None
股票买卖的最佳时机III
约束条件：最多买入K次股票，不准同时持有多支股票
解题思路：
- K为2时的情况
- 分为5个状态，分别为没有操作、第一次买入、第一次卖出、第二次买入、第二次卖出；即dp[i][j]表示第i天，j为[0-4]五个状态
- dp[i][1] = max(dp[i-1][0] - price[i], dp[i-1][1])
- dp[i][2] = max(dp[i-1][1] + price[i], dp[i-1][2])（同理可得dp[i][3]和dp[i][4]）
- K可为任何值时的通解
- 参考上述K=2时可以得出状态数为2*K+1个，分别讨论即可
# 买卖股票的最佳时机III def max_profit_3(prices, k=2): if len(prices) == 0: return 0 dp = [[0] * (2 * k + 1) for _ in range(len(prices))] for i in range(k): dp[i][1 + 2 * k] = -prices[0] for i in range(1, len(prices)): for j in range(0, 2 * k - 1, 2): dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]) dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]) return dp[-1][2 * k]
