写点什么

LeetCode 题解:714. 买卖股票的最佳时机含手续费,动态规划,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 03 月 06 日
LeetCode题解:714. 买卖股票的最佳时机含手续费,动态规划,JavaScript,详细注释

原题链接:714. 买卖股票的最佳时机含手续费


解题思路:


  1. 一共交易(prices.length天,因此可以创建同样长度的dp数组递推,每天有买卖两种状态,dp[i][0]为买,dp[i][1]为卖。

  2. i天可以做两种操作:


* 在i - 1天已卖出的基础上买入,表示为dp[i - 1][1] - prices[i]。同时第i天的买入状态,是0i天的最优解,因此买入的状态转移方程为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天的卖出状态,是0i天的最优解,因此卖出的状态转移方程为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];};
复制代码


发布于: 2021 年 03 月 06 日阅读数: 14
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:714. 买卖股票的最佳时机含手续费,动态规划,JavaScript,详细注释