带你读《图解算法小抄》二十一、动态规划（9）

带你读《图解算法小抄》二十一、动态规划（8）https://developer.aliyun.com/article/1347955?groupCode=tech_library

15.买卖股票的最佳时机 II

1）题目描述

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

**注意：**你不能同时进行多笔交易（即，你必须在再次购买之前出售掉之前的股票）。

2）解题步骤

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

• 定义状态：我们可以将问题转化为对于每个交易日的状态，即持有股票和未持有股票。令 dp[i][0] 表示第 i 天未持有股票时的最大利润，dp[i][1] 表示第 i 天持有股票时的最大利润。
  
• 初始状态：对于第一天，我们有以下初始状态：dp[0][0] = 0，因为第一天不持有股票，利润为0。
  
• dp[0][1] = -prices[0]，因为第一天持有股票，利润为买入价格的相反数。状态转移方程：对于第 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])
  

• 最终解：问题的解即为最后一天未持有股票时的最大利润，即 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];
}

带你读《图解算法小抄》二十一、动态规划（10）https://developer.aliyun.com/article/1347953?groupCode=tech_library