代码随想录算法训练营第四十一天 | 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机II、123. 买卖股票的最佳时机III

一、121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)——121. 买卖股票的最佳时机
视频讲解：动态规划之 LeetCode：121.买卖股票的最佳时机1_哔哩哔哩_bilibili

动态规划五部曲：

1. 确定 dp 数组及下标含义：dp[ i ][ 0 ] 表示持有这支股票得到最大的现金，dp[ i ][ 1 ] 表示不持有这支股票得到的最大的现金。由于卖出手头的钱一定比买入多，所以结果为 dp[ -1 ][ 1 ]
2. 确定递推公式：
dp[ i ][ 0 ] = max(dp[ i - 1 ][ 0 ], -price[ i ])，i 天之前就持有这支股票 和 第 i 天买入这支股票的最大值；
dp[ i ][ 1 ] = max(dp[ i - 1 ][ 0 ] + peice[ i ], dp[ i - 1][ 1 ])，i - 1天之前就持有这支股票并在第 i 天卖了 和 i 天之前就不持有这支股票的最大值。
3. 确定dp数组如何初始化：dp[ 0 ][ 0 ] = - price[ 0 ], dp[ 0 ][ 1 ] = 0
4. 确定遍历顺序：依赖前一个状态，从前往后遍历，其实为第二个价格
5. 举例推导dp数组。

class Solution:def maxProfit(self, prices: List[int]) -> int:# 创建dp数组dp = [[0] * 2 for _ in range(len(prices))]# 初始化dp[0][0] = -prices[0]dp[0][1] = 0for i in range(1, len(prices)):dp[i][0] = max(dp[i - 1][0], -prices[i])dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])return dp[-1][1]

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

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)——122.买卖股票的最佳时机II
视频讲解：动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II_哔哩哔哩_bilibili

Note：与上一题唯一的区别是由于股票可以买卖多次，dp[ i ][ 0 ] 中需要考虑 i - 1 天之前获得的利润，即 dp[ i ][ 0 ] = max(dp[ i - 1 ][ 0 ], dp[ i - 1][ 1 ] - price[ i ])，其余部分完全一致。

class Solution:def maxProfit(self, prices: List[int]) -> int:# 创建dp数组dp = [[0] * 2 for _ in range(len(prices))]# 初始化dp[0][0] = -prices[0]dp[0][1] = 0for i in range(1, len(prices)):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[-1][1]

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

题目链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)——123.买卖股票的最佳时机III
视频讲解：动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III_哔哩哔哩_bilibili

动态规划五部曲：

1. 确定 dp 数组及下标含义：dp[ i ][ 0 ] 表示不操作，dp[ i ][ 1 ] 表示第一次持有，
dp[ i ][ 2 ] 表示第一次不持有，dp[ i ][ 3 ] 表示第二次持有，dp[ i ][ 4 ] 表示第二次不持有，i 为第 i 天。由于卖出手头的钱一定比买入多且第二次卖出包含第一次卖出，所以最后输出 dp[ -1 ][ 4 ]。
2. 确定递推公式：
dp[ i ][ 0 ] = dp[ i-1 ][ 0 ]
dp[ i ][ 1 ] = max(dp[ i - 1 ][ 1 ], dp[ i-  1][ 0 ] - price[ i ])，可以保持前一天，也可以前一天不持有今天买入，即第一次持有
dp[ i ][ 2 ] = max(dp[ i - 1 ][ 2 ], dp[ i - 1][ 1 ] + price[ i ])，可以保持前一天，也可以前一天第一次持有今天卖出，即第一次卖出
dp[ i ][ 3 ] = max(dp[ i - 1 ][ 3 ], dp[ i -1 ][ 2 ] - price[ i ])，可以保持前一天，也可以前一天第一次不持有今天买入，即第二次持有
dp[ i ][ 4 ] = max(dp[ i - 1 ][ 4 ], dp[ i -1 ][ 3 ] + price[ i ])，可以保持前一天，也可以前一天第第二次持有今天卖出，即第二次卖出
3. 确定dp数组如何初始化：dp[ 0 ][ 0 ]  = 0, dp[ 0 ][ 1 ] = -price[ 0 ], dp[ 0 ][ 2 ] = 0（理解为同一天买卖）, dp[ 0 ][ 3 ] = -price[ 0 ], dp[ 0 ][ 4 ] = 0
4. 确定遍历顺序：正序遍历。
5. 举例推导dp数组。

class Solution:def maxProfit(self, prices: List[int]) -> int:# 创建dp数组dp = [[0] * 5 for _ in range(len(prices))]# 初始化dp[0][0] = 0dp[0][1] = -prices[0]dp[0][2] = 0dp[0][3] = -prices[0]dp[0][4] = 0for i in range(1, len(prices)):dp[i][0] = dp[ i-1 ][ 0 ]dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])return dp[-1][4]