当前位置： 面试刷题>> 带有冷却时间的买卖股票最佳时间 (经典算法题500道)
### 题目描述
在股票市场中，你有一个数组，其中第`i`个元素是一支给定股票第`i`天的价格。你设计一个算法来计算你所能获取的最大利润。但是，这次交易有一个额外的限制条件：你不能参与多笔交易（你必须在再次购买前出售掉之前的股票），并且你每进行一次交易（买入然后卖出）后，你必须在接下来的`cooldown`天内等待（即这`cooldown`天你不能进行任何交易，包括买入和卖出）。
例如，给定价格为`[1, 2, 3, 0, 2]`的数组，且`cooldown`时间为`1`，那么最优的交易方案可能是：
- 在第`1`天买入，价格为`1`；
- 在第`2`天卖出，价格为`2`，此时利润为`1`；
- 由于有`1`天的冷却时间，第`3`天不能交易；
- 在第`4`天买入，价格为`0`；
- 在第`5`天卖出，价格为`2`，此时再获得利润`2`。
因此，总的最大利润为`1 + 2 = 3`。
### PHP 示例代码
```php
function maxProfit($prices, $cooldown) {
$n = count($prices);
if ($n <= 1) return 0;
// dp[i][0] 表示第i天结束后不持有股票的最大利润
// dp[i][1] 表示第i天结束后持有股票的最大利润
// dp[i][2] 表示第i天处于冷却期的最大利润
$dp = array_fill(0, $n, array_fill(0, 3, 0));
$dp[0][0] = 0;
$dp[0][1] = -$prices[0];
$dp[0][2] = 0;
for ($i = 1; $i < $n; $i++) {
$dp[$i][0] = max($dp[$i-1][0], $dp[$i-1][2]); // 不持股，可以从前一天不持股或冷却期来
$dp[$i][1] = max($dp[$i-1][1], $dp[$i-1][0] - $prices[$i]); // 持股，可以前一天就持股或今天买入
$dp[$i][2] = $dp[$i-1][1] + $prices[$i]; // 冷却期，必须是前一天持股且今天卖出
}
return max($dp[$n-1][0], $dp[$n-1][2]); // 返回最后一天不持股或冷却期的最大利润
}
// 示例
$prices = [1, 2, 3, 0, 2];
$cooldown = 1;
echo maxProfit($prices, $cooldown); // 输出: 3
```
### Python 示例代码
```python
def maxProfit(prices, cooldown):
n = len(prices)
if n <= 1:
return 0
dp = [[0] * 3 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][2])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
dp[i][2] = dp[i-1][1] + prices[i] if i - cooldown - 1 >= 0 else 0
return max(dp[n-1][0], dp[n-1][2])
# 示例
prices = [1, 2, 3, 0, 2]
cooldown = 1
print(maxProfit(prices, cooldown)) # 输出: 3
```
### JavaScript 示例代码
```javascript
function maxProfit(prices, cooldown) {
const n = prices.length;
if (n <= 1) return 0;
const dp = new Array(n).fill(0).map(() => new Array(3).fill(0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (let i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
dp[i][2] = (i - cooldown - 1 >= 0) ? dp[i-1][1] + prices[i] : 0;
}
return Math.max(dp[n-1][0], dp[n-1][2]);
}
// 示例
const prices = [1, 2, 3, 0, 2];
const cooldown = 1;
console.log(maxProfit(prices, cooldown)); // 输出: 3
// 码小课网站中有更多相关内容分享给大家学习
```