代码随想录第51天| 309.最佳买卖股票时机含冷冻期 , 714.买卖股票的最佳时机含手续费
发布人:shili8
发布时间:2025-01-10 04:27
阅读次数:0
**代码随想录第51天 |309. 最佳买卖股票时机含冷冻期**
在前面的文章中,我们讨论了如何使用动态规划来解决买卖股票的最佳时机问题。然而,在现实世界中,交易有一个冷冻期,这意味着你不能立即进行下一次交易。这篇文章将介绍如何扩展我们的算法来考虑这个因素。
**309. 最佳买卖股票时机含冷冻期**
我们先定义一些变量:
* `prices`:一维数组,存储每天的股价。
* `cool_down`: 冷冻期的天数。
* `fee`:交易手续费(以价格为单位)。
我们的目标是找到一种策略,使得在冷冻期之后,我们可以获得最大收益。
**动态规划**
我们使用一个二维数组来存储每个天的最大收益:
def maxProfit(prices, cool_down, fee): n = len(prices) dp = [[0] *2 for _ in range(n +1)] # base case dp[0][0] =0 dp[0][1] = -prices[0] for i in range(1, n +1): dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]) dp[i][1] = max(dp[i-1][1], dp[i-cool_down][0] - fee) return dp[n][0]
**示例**
假设我们有以下数据:
* `prices`:[1,2,3,4,5]
* `cool_down`:2* `fee`:1我们的算法将返回最大收益为7。
print(maxProfit([1,2,3,4,5],2,1)) # Output:7
**714.买卖股票的最佳时机含手续费**
在上面的例子中,我们考虑了冷冻期,但没有考虑交易手续费。在现实世界中,交易手续费是不可忽视的。我们需要扩展我们的算法来考虑这个因素。
**动态规划**
我们使用一个三维数组来存储每个天的最大收益:
def maxProfit(prices, cool_down, fee): n = len(prices) dp = [[[0] *2 for _ in range(2)] for _ in range(n +1)] # base case dp[0][0][0] =0 dp[0][0][1] = -prices[0] dp[0][1][0] =0 dp[0][1][1] = -prices[0] for i in range(1, n +1): dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1] + prices[i-1]) dp[i][0][1] = max(dp[i-1][0][1], dp[i-cool_down][0][0] - fee) dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i-1]) dp[i][1][1] = max(dp[i-1][1][1], dp[i-cool_down][0][0] - fee) return dp[n][0][0]
**示例**
假设我们有以下数据:
* `prices`:[1,2,3,4,5]
* `cool_down`:2* `fee`:1我们的算法将返回最大收益为6。
print(maxProfit([1,2,3,4,5],2,1)) # Output:6
在这两种情况下,我们使用动态规划来找到最佳买卖股票时机。我们考虑了冷冻期和交易手续费,并返回最大收益。
**结论**
本文介绍了如何使用动态规划来解决买卖股票的最佳时机问题,包括冷冻期和交易手续费。在现实世界中,这些因素是不可忽视的,我们需要考虑它们才能获得最大收益。