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