LeetCode 123. Best Time to Buy and Sell Stock III 题解

LeetCode 123. Best Time to Buy and Sell Stock III 题解题目描述给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1输入prices [3,3,5,0,0,3,1,4] 输出6 解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。 随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。示例 2输入prices [1,2,3,4,5] 输出4 解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。示例 3输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 没有交易完成, 所以最大利润为 0。解题思路方法动态规划思路动态规划的核心思想是将原问题分解为子问题并存储子问题的解以避免重复计算。对于买卖股票的最佳时机 III 问题我们可以定义以下状态dp[i][0]第 i 天不持有股票且没有进行过任何交易的最大利润。dp[i][1]第 i 天持有股票且进行过一次买入的最大利润。dp[i][2]第 i 天不持有股票且进行过一次买卖的最大利润。dp[i][3]第 i 天持有股票且进行过一次买卖和一次买入的最大利润。dp[i][4]第 i 天不持有股票且进行过两次买卖的最大利润。状态转移方程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])边界条件dp[0][0] 0dp[0][1] -prices[0]dp[0][2] 0dp[0][3] -prices[0]dp[0][4] 0最终结果是max(dp[n-1][0], dp[n-1][2], dp[n-1][4])其中 n 是数组的长度。复杂度分析时间复杂度O(n)其中 n 是数组的长度。只需要遍历一次数组。空间复杂度O(n)需要使用一个 n x 5 的二维数组来存储 dp 值。代码实现方法动态规划class Solution: def maxProfit(self, prices: List[int]) - int: # 处理边界情况 if not prices: return 0 # 初始化 dp 数组 n len(prices) dp [[0] * 5 for _ in range(n)] dp[0][0] 0 # 不持有股票没有交易 dp[0][1] -prices[0] # 持有股票一次买入 dp[0][2] 0 # 不持有股票一次买卖 dp[0][3] -prices[0] # 持有股票一次买卖一次买入 dp[0][4] 0 # 不持有股票两次买卖 # 计算 dp[i][*] for i in range(1, n): 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 max(dp[n-1][0], dp[n-1][2], dp[n-1][4])测试用例测试用例 1输入prices [3,3,5,0,0,3,1,4]输出6测试用例 2输入prices [1,2,3,4,5]输出4测试用例 3输入prices [7,6,4,3,1]输出0总结本题是动态规划的经典问题主要考察对动态规划思想的理解和应用。通过定义状态和状态转移方程我们可以高效地计算出最多完成两笔交易的最大利润。动态规划的核心思想是将原问题分解为子问题并存储子问题的解以避免重复计算。这种方法不仅适用于买卖股票的最佳时机 III 问题还可以应用于许多其他需要递推的问题。掌握动态规划的原理对于理解算法设计思想非常重要。