动态规划
解题思路
确定 dp 数组以及下标的含义：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润，其中：
- 若 j = 0，表示当前不持股；
- 若 j = 1，表示当前持股；
确定递推公式：
- dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])：表示当前不持股；
- dp[i - 1][0]：昨天不持股，今天不操作；
- dp[i - 1][1] + prices[i]：昨天持股，今天卖出；
- dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)：表示当前持股；
- dp[i - 1][1]：：昨天持股，今天不操作；
- dp[i - 1][0] - prices[i] - fee：昨天不持股，今天买入，需要手续费（手续费买入或卖出时考虑都可以）；
如何初始化 dp 数组：
- 第 0 天不持有：dp[0][0] = 0；
- 第 0 天持有：dp[0][1] = -prices[0] - fee；
确定遍历顺序：从递推公式可以看出 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 2 2 3 3dp[i][1] 规定了今天 持股 -9 -3 -3 -3 -3 -3
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：状态压缩之前是
O(n)，状态压缩后是O(1)；
代码实现
JavaScript
JavaScript
const maxProfit = (prices, fee) => {
const len = prices.length;
if (len < 2) {
return 0;
}
const dp = new Array(len).fill(0).map(it => new Array(2).fill(0));
dp[0][0] = 0;
dp[0][1] = -prices[0] - fee;
for (let i = 1; i < len; 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][0] - prices[i] - fee);
}
return dp[len - 1][0];
};
const maxProfit = (prices, fee) => {
const len = prices.length;
if (len < 2) {
return 0;
}
const dp = new Array(2).fill(0);
dp[0] = 0;
dp[1] = -prices[0] - fee;
for (let i = 1; i < len; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i]);
dp[1] = Math.max(dp[1], dp[0] - prices[i] - fee);
}
return dp[0];
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 188. 买卖股票的最佳时机 IV
上一篇
评论
