买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i][j] 当 i=0 时，表示第 j 天持有股票时的利润 ,当 i=1 时，表示第 j 天不持有股票时的利润。

2.初始化 dp 数组，dp[0][0] = -prices[0], dp[1][0] = 0。

3.确定遍历方向，从前往后遍历。

4.确定转移方程，当第 i 天，处于持有股票时的利润，则为第 i-1 天，持有股票的利润和第 i-1 天，不持有股票的利润-当前价格 的最大值。当第 i 天，处于不持有股票时的利润，为第 i-1 天不持有股票的利润和第 i-1 天持有股票的利润+当前价格-手续费 的最大值。即 dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] - prices[i]), dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] + prices[i] - fee)。

5.确定结束条件，遍历到最后一天，此时最后一天不持有股票的利润是最大的，返回 dp[1][days - 1] 即可。

typescript 解法

function maxProfit(prices: number[], fee: number): number {
  const days: number = prices.length;
  // 确定dp数组含义，dp[i][j], 当i=0时，表示第j天持有股票时的利润 ,当i=1时，表示第j天不持有股票时的利润。
  const dp: number[][] = new Array(2)
    .fill(0)
    .map(() => new Array(days).fill(0));
  // 初始化dp数组
  dp[0][0] = -prices[0];
  dp[1][0] = 0;
  // 确定遍历方向
  for (let i = 1; i < days; i++) {
    // 确定转移方程
    dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] - prices[i]);
    dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] + prices[i] - fee);
  }
  return dp[1][days - 1];
}

go 解法

func maxProfit(prices []int, fee int) int {
    // dp[i][j] 当i为0时，表示第j天持有股票时的利润， 当i为1时，表示第j天不持有股票时（即已卖出或者当天卖出）时的利润。
    days := len(prices)
    dp := make([][]int, 2)
    // 初始化dp数组
    dp[0] = make([]int, days)
    dp[1] = make([]int, days)
    dp[0][0] = -prices[0]
    dp[1][0] = 0
    // 确定遍历方向
    for i := 1; i < days; i ++ {
        // 确定转换方程，
        // 当第i天，处于持有股票时的利润，则为第i-1天，持有股票的利润和第i-1 天，不持有股票的利润-当前价格 的最大值
        dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i])
        // 当第i天，处于不持有股票时的利润，为第i-1天不持有股票的利润和第i-1天持有股票的利润+当前价格-手续费 的最大值。
        dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i] - fee)
    }
    return dp[1][days - 1];
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}