188.md

dp[i][j] 代表在第 j 天最多交易 i 次获得的最大利润

在第 j 天，我们有两个选择

• 不做任何不改变获得利润的事(无操作或买入): dp[i][j] = dp[i][j-1] .

• 卖掉股票: dp[i][j] = max(prices[j]-prices[t]+dp[i-1][t-1]) 其中 t=[0..j-1] .

所以核心代码如下

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

题解如下:

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
const maxProfit = function (k, prices) {
  let n = prices.length,
    res = 0;
  if (n <= 1)
    return 0;
  if (k >= n / 2)
    return maxProfit2(prices);
  let dp = [];
  for (let i = 0; i <= k; i++) {
    dp[i] = [];
    for (let j = 0; j < n; j++) {
      dp[i][j] = 0;
    }
  }
  for (let i = 1; i <= k; i++) {
    let tempMax = -prices[0];
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.max(dp[i][j - 1], tempMax + prices[j]);
      tempMax = Math.max(tempMax, dp[i - 1][j - 1] - prices[j]);
    }
  }
  return dp[k][n - 1];
};

const maxProfit2 = function (prices) {
  const n = prices.length;
  let res = 0;
  for (let i = 1; i < n; i++)
    if (prices[i] - prices[i - 1] > 0)
      res += prices[i] - prices[i - 1];
  return res;
}

附一个这题的系列题目的解析:https://blog.csdn.net/Dr_Unknown/article/details/51939121