题目描述

在股票市场中，你有一个数组，其中第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 示例代码

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 示例代码

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 示例代码

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

// 码小课网站中有更多相关内容分享给大家学习