跳至主要內容

买卖股票的最佳时机 II

linwu大约 2 分钟

买卖股票的最佳时机 II

题目描述

给定一个数组 prices,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

**注意:**你不能同时进行多笔交易(即,你必须在再次购买之前出售掉之前的股票)。

解题步骤

为了计算买卖股票的最佳时机 II,我们可以使用动态规划的思想来解决问题。

  1. 定义状态:我们可以将问题转化为对于每个交易日的状态,即持有股票和未持有股票。令 dp[i][0] 表示第 i 天未持有股票时的最大利润,dp[i][1] 表示第 i 天持有股票时的最大利润。

  2. 初始状态:对于第一天,我们有以下初始状态:

    • dp[0][0] = 0,因为第一天不持有股票,利润为0。
    • dp[0][1] = -prices[0],因为第一天持有股票,利润为买入价格的相反数。
  3. 状态转移方程:对于第 i 天,我们可以进行以下操作:

    • 如果第 i 天未持有股票,那么最大利润为前一天未持有股票的最大利润 dp[i-1][0],或者前一天持有股票并在第 i 天卖出所得到的利润 dp[i-1][1] + prices[i] 中的较大值。
    • 如果第 i 天持有股票,那么最大利润为前一天持有股票的最大利润 dp[i-1][1],或者前一天未持有股票并在第 i 天买入所得到的利润 dp[i-1][0] - prices[i] 中的较大值。

    综上所述,我们可以得到状态转移方程为:

    • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
  4. 最终解:问题的解即为最后一天未持有股票时的最大利润,即 dp[n-1][0],其中 n 是交易日的总数。

下面是使用动态规划解决买卖股票的最佳时机 II 问题的算法框架:

function maxProfit(prices) {
  const n = prices.length;

  if (n < 2) {
    return 0;
  }

  const dp = new Array(n).fill(0).map(() => new Array(2).fill(0));

  dp[0][0] = 0;
  dp[0][1] = -prices[0];

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  }

  return dp[n - 1][0];
}

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群