LeetCode题解:714. 买卖股票的最佳时机含手续费,动态规划,JavaScript,详细注释
chencl1986 opened this issue · 0 comments
chencl1986 commented
原题链接:714. 买卖股票的最佳时机含手续费
解题思路:
-
一共交易
(prices.length
天,因此可以创建同样长度的dp
数组递推,每天有买卖两种状态,dp[i][0]为买,dp[i][1]为卖。 -
第
i
天可以做两种操作:- 在
i - 1
天已卖出的基础上买入,表示为dp[i - 1][1] - prices[i]
。同时第i
天的买入状态,是0
到i
天的最优解,因此买入的状态转移方程为dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
。 - 在
i - 1
天已买入的基础上卖出,表示为dp[i - 1][0] + prices[i]
。由于每次卖出需要支付手续费,因此要表示为dp[i - 1][0] + prices[i] - fee
。同时第i
天的卖出状态,是0
到i
天的最优解,因此卖出的状态转移方程为dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
。
- 在
/**
* @param {number[]} prices
* @param {number} fee
* @return {number}
*/
var maxProfit = function (prices, fee) {
// 共有prices.length天的状态,创建相应长度的数组递推
// 每天可以做买卖两种操作,dp[i][0]为买,dp[i][1]为卖
let dp = new Array(prices.length);
// 第0天只能买不能卖
dp[0] = [-prices[0], 0];
// 从第1天开始递推
for (let i = 1; i < prices.length; i++) {
dp[i] = [
// 递推第i天的买入的状态
Math.max(
dp[i - 1][0], // 0~i-1天买入的状态
dp[i - 1][1] - prices[i], // i-1天卖出,第i天买入的状态
),
// 递推第i天的卖出的状态
Math.max(
dp[i - 1][1], // 0~i-1天卖出的状态
dp[i - 1][0] + prices[i] - fee, // i-1天买入,第i天卖出的状态,卖出需要扣除手续费
),
];
}
// 最后一天的卖出状态,就是总利润
return dp[dp.length - 1][1];
};