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

[chencl1986]

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

解题思路：

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

2. 第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];
};