代码随想录算法训练营day51 | 动态规划 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费

**代码随想录算法训练营 Day51 | 动态规划**

在前面的日子里，我们已经学习了动态规划（Dynamic Programming）这个重要的算法思想。今天，我们将继续深入探讨这个主题，并应用它来解决两个经典的问题：309. 最佳买卖股票时机含冷冻期 和714.买卖股票的最佳时机含手续费。

###问题309: 最佳买卖股票时机含冷冻期给定一个数组 `prices`，其中每个元素代表一天的股价，我们需要找到最好的买卖时机，以便在冷冻期（即买入后不能立即卖出）之后获得最大收益。

**示例1:**

* `prices = [7,1,5,3,6,8]`
* 最佳买卖时机：买入于第2 天（价格为1 美元），卖出于第5 天（价格为8 美元）
* 最大收益：8 -1 =7**示例2:**

* `prices = [1,2,3,4,5]`
* 最佳买卖时机：买入于第1 天（价格为1 美元），卖出于第5 天（价格为5 美元）
* 最大收益：5 -1 =4###问题714:买卖股票的最佳时机含手续费给定一个数组 `prices`，其中每个元素代表一天的股价，我们需要找到最好的买卖时机，以便在手续费（即买入或卖出时支付的费用）之后获得最大收益。

**示例1:**

* `prices = [7,1,5,3,6,8]`
* 手续费：每次交易（买入或卖出）支付2 美元的手续费* 最佳买卖时机：买入于第2 天（价格为1 美元），卖出于第5 天（价格为6 美元）
* 最大收益：6 -1 =5**示例2:**

* `prices = [1,2,3,4,5]`
* 手续费：每次交易（买入或卖出）支付2 美元的手续费* 最佳买卖时机：买入于第1 天（价格为1 美元），卖出于第5 天（价格为5 美元）
* 最大收益：5 -1 =4### 解决方案我们将使用动态规划来解决这两个问题。动态规划是一种通过分解问题并求解子问题的方法来解决复杂的问题。

####309. 最佳买卖股票时机含冷冻期

def maxProfit(prices):
 if not prices:
 return0 # dp[i][0] 表示第 i 天结束后，最大收益为0 的情况 # dp[i][1] 表示第 i 天结束后，最大收益为1 的情况 dp = [[0,0] for _ in range(len(prices))]
 # 初始化 base case dp[0][0] =0 dp[0][1] = -prices[0]
 # 动态规划 for 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], -prices[i])
 return dp[-1][0]

def maxProfit(prices, fee):
 if not prices:
 return0 # dp[i][0] 表示第 i 天结束后，最大收益为0 的情况 # dp[i][1] 表示第 i 天结束后，最大收益为1 的情况 # dp[i][2] 表示第 i 天结束后，最大收益为2 的情况 dp = [[0,0,0] for _ in range(len(prices))]
 # 初始化 base case dp[0][0] =0 dp[0][1] = -prices[0]
 dp[0][2] = float('-inf')
 # 动态规划 for i in range(1, len(prices)):
 dp[i][0] = max(dp[i-1][0], dp[i-1][1])
 dp[i][1] = max(dp[i-1][1], dp[i-1][2] + prices[i] - fee)
 dp[i][2] = max(dp[i-1][2], dp[i-1][0] - fee)
 return dp[-1][0]