动态规划
解题思路
在 leetcode🧑💻 122. 买卖股票的最佳时机Ⅱ 的基础上增加了 冷冻期；
确定 dp 数组以及下标的含义：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润，其中：
- 若 j = 0，表示当前不持股（冷冻期）；
- 若 j = 1，表示当前持股；
- 若 j = 2，表示当前不持股（正常卖出）；
确定递推公式：
- dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2])：当前不持股（冷冻期）；
- dp[i - 1][0]：昨天不持股（冷冻期），今天不操作；
- dp[i - 1][2]：昨天不持股（正常卖出），今天不操作；
- dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])：当前持股；
- dp[i - 1][1]：：昨天买入，今天不操作；
- dp[i - 1][0] - prices[i]：昨天不持股（冷冻期），今天买入；
- dp[i][2] = dp[i - 1][1] + prices[i]：表示当前不持股（正常卖出）；
如何初始化 dp 数组：
- 第 0 天不持有（冷冻期）：dp[0][0] = 0；
- 第 0 天持有：dp[0][1] = -prices[0]；
- 第 0 天不持有（正常卖出）：dp[0][2] = 0；
确定遍历顺序：从递推公式可以看出 dp[i] 都是由 dp[i - 1] 推导出来的，那么一定是从前向后遍历；
举例推导 dp 数组：以 prices = [7, 1, 5, 3, 6, 4] 为例：
索引 i = 0 索引 i = 1 索引 i = 2 索引 i = 3 索引 i = 4 索引 i = 5 dp[i][0] 规定了今天 不持股（冷冻期） 0 0 0 4 4 5dp[i][1] 规定了今天 持股 -7 -1 -1 -1 -1 0 dp[i][2] 规定了今天 不持股（正常卖出） 0 -6 4 2 5 3
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：状态压缩之前是
O(n)，状态压缩后是O(1)；
实现代码
JavaScript
JavaScript
const maxProfit = (prices) => {
const len = prices.length;
if (prices.length < 2) {
return 0;
}
let dp = new Array(len).fill(0).map(it => new Array(3).fill(0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (let i = 1; i < len; i++) {
// dp[i][0]: 手上不持有股票，并且今天不是由于卖出股票而不持股，拥有的现金数
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
// dp[i][1]: 手上持有股票时，拥有的现金数
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
// dp[i][2]: 手上不持有股票，并且今天是由于卖出股票而不持股，拥有的现金数
dp[i][2] = dp[i - 1][1] + prices[i];
}
// 最后的结果由 「当前不持股（冷冻期）」、「当前不持股（正常卖出）」 推出，选择最大值
return Math.max(dp[len - 1][0], dp[len - 1][2]);
};
const maxProfit = (prices) => {
const len = prices.length;
if (len < 2) {
return 0;
}
let dp = new Array(2).fill(0).map(it => new Array(3).fill(0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (let i = 1; i < len; i++) {
dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][2]);
dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] - prices[i]);
dp[i % 2][2] = dp[(i - 1) % 2][1] + prices[i];
}
return Math.max(dp[(len - 1) % 2][0], dp[(len - 1) % 2][2]);
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 714. 买卖股票的最佳时机含手续费
上一篇
评论
