买卖股票系列

• 121.买卖股票的最佳时机
• 122.买卖股票的最佳时机 II
• 123.买卖股票的最佳时机 III
• 188.买卖股票的最佳时机 IV
• 309.最佳买卖股票时机含冷冻期
• 714.买卖股票的最佳时机含手续费

解题思路

和打家劫舍一样，主要是分析出每天有多少种情况，构建出每个情况的状态转移方程，做动态规划题的关键还是不要去想怎么买和卖，买和卖交给规划去决定

买卖股票的最佳时机 IV

给定一个整数数组prices ，它的第i个元素prices[i]是一支给定的股票在第i天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。

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

代码实现

var maxProfit = function (k, prices) {
  // dp[i][j] 表示第 i 天，最多进行 j 次交易，当前持有状态为 k 时的最大收益
  const dp = new Array(prices.length).fill(0).map(() => new Array(2 * k + 1).fill(0));
  for (let j = 1; j < 2 * k; j += 2) {
    dp[0][j] = 0 - prices[0];
  }

  for (let i = 1; i < prices.length; i++) {
    dp[i][0] = dp[i - 1][0];
    for (let j = 1; j < 2 * k + 1; j += 2) {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
      dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
    }
  }
  return dp[prices.length - 1][2 * k];
};

最佳买卖股票时机含冷冻期

给定一个整数数组，其中第i个元素代表了第i天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为1天)。

代码实现

var maxProfit = function (prices) {
  const dp = new Array(prices.length).fill(0).map(() => new Array(3).fill(0));
  //dp[i][0] 表示第 i 天，持有股票时的最大收益
  //dp[i][1] 表示第 i 天，不持有股票时的最大收益且不处于冷冻期
  //dp[i][2] 表示第 i 天，不持有股票时的最大收益且处于冷冻期
  dp[0][0] = -prices[0];
  for (let i = 1; i < prices.length; 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][2]);
    dp[i][2] = dp[i - 1][0] + prices[i];
  }
  return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
};