LeetCode 题解:714. 买卖股票的最佳时机含手续费,动态规划,JavaScript,详细注释
原题链接: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);
。
复制代码
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/4fad6d9eaad165e736b88e36d】。文章转载请联系作者。
评论