问题

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费

示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路

相对于leetcode-122：买卖股票的最佳时机Ⅱ，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的
唯一差别在于递推公式部分，所以主要讲解一下递推公式部分

这里重申一下dp数组的含义：
dp[i][0]表示第i天持有股票所省最多现金。dp[i][1]表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金是昨天不持有股票的所得现金减去今天的股票价格 即：dp[i - 1][1] - prices[i]
  • dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来

  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee

  • dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

    1. class Solution {
    2.   public int maxProfit(int[] prices, int fee) {
    3.       int n = prices.length;
    5.       int[][] dp = new int[n][2];
    6.       dp[0][0] -= prices[0]; // 持股票
    8.       for (int i = 1; i < n; i++) {
    9.           dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
    10.           dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
    11.       }
    12.       return Math.max(dp[n - 1][0], dp[n - 1][1]);
    13.   }
    14. }

  • 时间复杂度：O(n)

  • 空间复杂度：O(n)