LeetCode 股票系列（三）

今天我们来继续聊聊 Leetcode 的华尔街之狼（The Wolf of Wall Street）系列，也称股票系列， 在 Leetcode 上有 6 题之多。

今天讲解的是第三题，与前两题相比升级了一点难度，我们一起来看下。

3. Best Time to Buy and Sell Stock with Transaction Fee && Best Time to Buy and Sell Stock II

题意：

同样还是给你一组数组代表每一天的股价，这次我们可以进行多次买卖，但是每一次买卖你需要多付一个fee。例如，prices = [1,3,2,8,4,9], fee = 2

我们可以在第1天买第4天卖和第5天买第6天卖，总收益是(8-1-2) + (9-4-2) = 8，这是我们能得到的最大收益。

这里我们两题一起讲，因为他们是一样的，Best Time to Buy and Sell Stock II 其实就是fee=0 的情况，如果我们能做出Best Time to Buy and Sell Stock with Transaction Fee，Best Time to Buy and Sell Stock II 就迎刃而解了。

问题分析 ：

与之前的问题一样，我们可以试着枚举买或者卖。

但是因为这次不只是只有一次操作这么简单，如果我们在 j 天进行购买和 i 天进行卖 (j<i), prices[0 : j-1] 可能还存在着其它的交易。

我们试着像第一题的方法1一样先从暴力入手，去试着枚举 （买，卖） pair。

如果我们在i天进行卖和j天进行买，他的单次交易 (singleTransaction) 能得到的利益是 prices[i]-prices[j]-fee。

但我们别忘了，我们prices[0 : j-1] 还可以进行其它的交易。

所以我们可以用一个 dp 去记录，dp[i] 表示 prices[0:i] 能得到的最大收益。

所以如果我们在 i天卖和在j 天买，那么我们能得到的最大收益就是 prices[i]-prices[j]-fee+dp[j-1]。

现在我们剩下的问题就是如何去计算dp[i]，如果我们在i 天进行卖，j 进行买，那么如果我们枚举所有 j 的 可能性的话，dp[i]=max(prices[i] - prices[j]-fee + dp[j-1])。

但是我们别忘了一件事，我们在i 这天也可以不进行任何的操作，所以还要跟 dp[i-1] 进行比较。

综上，dp[i]=max(dp[i-1], max(prices[i] - prices[j]-fee + dp[j-1]))

方法1：暴力解

public int maxProfit(int[] prices, int fee) {
   int n = prices.length;
   int dp[] = new int[n];//dp[i]表示 [0:i]的最大收益
   for (int i = 1; i < n; i++) {//枚举i,i是卖的天数
     dp[i] = dp[i - 1];
     for (int j = i - 1; j >= 0; j--) {//j 是买的天数，j<i
       int singleTransaction = Math.max(0, prices[i] - prices[j] - fee);
       //注意outbound
       if (j - 1 >= 0) {
         dp[i] = Math.max(dp[i], singleTransaction + dp[j - 1]);
       } else {
         dp[i] = Math.max(dp[i], singleTransaction);
       }
     }
   }
   return dp[n - 1];
 }

代码总结：

• 暴力的dp，我们还会通过仔细观察 dp 的关系转移去进行深一步的优化

空间复杂度和时间复杂度：

• 时间复杂度：O(N^2)
• 空间复杂度：O(N)

方法2：优化DP

我们可以从 dp 的关系转移中进行优化：

从方法1我们可以看出 dp[i]=max(dp[i-1], max(prices[i] - prices[j]-fee + dp[j-1]))，从这转移式中我们可以发现 i 是一个不变量，而 j 是变量。

首先，我们设dp[i]=dp[i-1]。

我们再仔细的观察一下这个式子 prices[i] - prices[j]-fee + dp[j-1]，当我们枚举 i 的时候，我们会发现prices[i] - fee 是个常数！

我们如果把式子重新整理一下，那它就是 (prices[i] - fee) - (prices[j] - dp[j-1])。

我们要是想整个式子的值越大，变量部分prices[j] - dp[j-1] 就得越小。

如果我们在 i 进行卖，dp[i] = (prices[i] - fee) - min(prices[j] - dp[j-1])，我们可以用一个min 去记录 prices[j] - dp[j-1]，一边遍历一边update。

没错，跟第一题的操作是完全一样的。

public int maxProfit(int[] A, int fee) {
  int n = A.length;
  int dp[] = new int[n];
  int min = A[0];
  for (int i = 1; i < A.length; i++) {
    int cur = A[i] - fee;
    dp[i] = dp[i - 1];
    dp[i] = Math.max(dp[i], cur - min);
    min = Math.min(min, A[i] - dp[i - 1]); 
  }
  return dp[n - 1];
}

代码总结：

• DP 其实就是一种关系(式子)的转化，当我们求出他的基本关系的时候，我们可以看看能不能通过它的关系进行优化

空间复杂度和时间复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)