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

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

16.买卖股票的最佳时机 III

1）题目描述

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

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

2）解题步骤

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

• 定义状态：我们可以将问题转化为对于每个交易日的状态，即持有股票和未持有股票。令 dp[i][j][k] 表示第 i 天，已完成 j 笔交易，并且处于状态 k（0 表示未持有股票，1 表示持有股票）时的最大利润。
  
• 初始状态：对于第一天，我们有以下初始状态：dp[0][0][0] = 0，第一天未持有股票时的最大利润为 0。
  
• dp[0][1][0] = 0，第一天完成了一笔交易，但未持有股票时的最大利润为 0。
  
• dp[0][0][1] = -prices[0]，第一天持有股票时的最大利润为买入价格的相反数。
  
• dp[0][1][1] = -prices[0]，第一天完成了一笔交易且持有股票时的最大利润为买入价格的相反数。
  

• 状态转移方程：对于第 i 天，我们可以进行以下操作：如果第 i 天未持有股票且未完成任何交易（k = 0, j = 0），那么最大利润为前一天未持有股票且未完成任何交易的最大利润 dp[i-1][0][0]。
  
• 如果第 i 天未持有股票但已完成一笔交易（k = 0, j = 1），那么最大利润为前一天未持有股票但已完成一笔交易的最大利润 dp[i-1][1][0] 加上在第 i 天卖出股票所得到的利润 prices[i]。
  
• 如果第 i 天持有股票且未完成任何交易（k = 1, j = 0），那么最大利润为前一天持有股票且未完成任何交易的最大利润 dp[i-1][0][1]。
  
• 如果第 i 天持有股票且已完成一笔交易（k = 1, j = 1），那么最大利润为前一天持有股票且已完成一笔交易的最大利润 dp[i-1][1][1] 加上在第 i 天卖出股票所得到的利润 prices[i]。
  

• 综上所述，我们可以得到状态转移方程为：
  
• dp[i][0][0] = dp[i-1][0][0]
  
• dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i])
  
• dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i])
  
• dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] - prices[i])
  

• 最终解：问题的解即为最后一天未持有股票且已完成两笔交易时的最大利润，即 dp[n-1][1][0]，其中 n 是交易日的总数。
  

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

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).map(() => new Array(3).fill(0))
  );  dp[0][0][0] = 0;
  dp[0][1][0] = 0;
  dp[0][0][1] = -prices[0];
  dp[0][1][1] = -prices[0];  for (let i = 1; i < n; i++) {
    dp[i][0][0] = dp[i - 1][0][0];
    dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][0][0] - prices[i]);
    dp[i][0][1] = Math.max(dp[i - 1][0][1], dp[i - 1][1][0] + prices[i]);
    dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][1] - prices[i]);
  }  return dp[n - 1][1][0];
}

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