买卖股票的最佳时机 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];
}