代码随想录算法训练营Day 49 || 123.买卖股票的最佳时机III 、188.买卖股票的最佳时机IV
123.买卖股票的最佳时机III
力扣题目链接(opens new window)
给定一个数组，它的第 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。
-
示例 4：
-
输入：prices = [1] 输出：0
提示：
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
解题思路：
-
定义状态： 由于最多可以进行两笔交易，我们需要跟踪四个状态：第一次买入（
first_buy）、第一次卖出（first_sell）、第二次买入（second_buy）、第二次卖出（second_sell）。 -
初始化状态：
first_buy初始化为负无穷大，因为还没有进行任何买入操作。first_sell、second_buy、second_sell都初始化为0，因为初始利润为0。
-
状态转移：
- 对于每一天的价格，更新上述四个状态。
first_buy：选择之前的first_buy或者当天的价格（负数，因为是花费）中的较大者。first_sell：选择之前的first_sell或者今天的价格加上first_buy（代表卖出）中的较大者。second_buy：选择之前的second_buy或者first_sell减去今天的价格中的较大者。second_sell：选择之前的second_sell或者今天的价格加上second_buy中的较大者。
-
计算结果：
- 遍历完所有价格后，
second_sell就是最大利润。
- 遍历完所有价格后，
class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices:return 0first_buy, first_sell = -float('inf'), 0second_buy, second_sell = -float('inf'), 0for price in prices:first_buy = max(first_buy, -price) # 第一次买入的最佳选择first_sell = max(first_sell, first_buy + price) # 第一次卖出的最佳选择second_buy = max(second_buy, first_sell - price) # 第二次买入的最佳选择second_sell = max(second_sell, second_buy + price) # 第二次卖出的最佳选择return second_sell # 返回最大利润
188.买卖股票的最佳时机IV
力扣题目链接
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
-
示例 1：
-
输入：k = 2, prices = [2,4,1]
-
输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。
-
示例 2：
-
输入：k = 2, prices = [3,2,6,5,0,3]
-
输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示：
- 0 <= k <= 100
- 0 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
解题思路：
-
状态定义： 定义
dp[i][j]作为一个二维数组，其中i表示天数，j表示交易次数（每次交易包括买和卖两个动作）。dp[i][j]表示第i天完成j笔交易能获得的最大利润。 -
初始化：
- 对于
dp[0][..]（即第0天），无论交易次数如何，利润都是0，因为没有交易发生。 - 对于
dp[..][0]（即没有交易），无论天数如何，利润都是0。
- 对于
-
状态转移：
- 需要决定第
i天是买入、卖出还是不操作。这可以通过比较不同选择下的利润来决定。 - 对于买入操作，我们要找到之前某天
m，使得dp[m][j-1] - prices[i]（即第m天完成j-1笔交易后的利润减去第i天的股价）最大。 - 对于卖出操作，我们要找到之前某天
m，使得dp[m][j-1] + prices[i]最大。 - 对于不操作，直接保持前一天的状态，即
dp[i][j] = dp[i-1][j]。
- 需要决定第
-
结果计算：
- 最后
dp[n-1][k]（其中n是天数）就是在给定的条件下可以获得的最大利润。
- 最后
class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:if not prices:return 0n = len(prices)if k >= n // 2:return self.maxProfitInf(prices)dp = [[0] * (k + 1) for _ in range(n)]for j in range(1, k + 1):max_diff = -prices[0]for i in range(1, n):dp[i][j] = max(dp[i-1][j], prices[i] + max_diff)max_diff = max(max_diff, dp[i-1][j-1] - prices[i])return dp[-1][-1]def maxProfitInf(self, prices: List[int]) -> int:profit = 0for i in range(1, len(prices)):if prices[i] > prices[i-1]:profit += prices[i] - prices[i-1]return profit