LeetCode 股票系列（四）

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

今天讲解的是第四题，如果你会了第三题的解法，你会发现这题与上一题其实是异曲同工。

4. Best Time to Buy and Sell Stock with Cooldown

题意：

给你一个数组prices = [1,2,3,0,2]，你可以进行多次交易，但每完成一次交易得有一个cooldown，不能连续做交易

按照以上的数据，如果我们按这样的操作[buy, sell, cooldown, buy, sell] 我们能够得到利益 (2 - 1) + (2 - 0) =3，这是我们能够得到的最大利益

问题分析 ：

• 因为有多次交易的关系，我们可以像上一题那样，使dp[i] 表示 prices[0 : i] 的最大收益。如果我们在 i 这天进行卖 和 j 这天进行买，我们能得到的收益就是 prices[i]-prices[j] + dp[j-2]
  
• 剩下的问题就是define dp[i]。我们首先dp[i]=dp[i-1]，因为在i这天我们可以不进行任何操作。然后我们要找的就是 max(prices[i] - prices[j] +dp[j-2])
  
• 和上一题一样，当我们在i 这天时，prices[i] 是个常数。我们只需要找到最大的 (-prices[j]+dp[j-2]) 即可，我们可以像上题一样一边计算一边记录

代码：

public int maxProfit(int[] A) {
  if (A.length == 0) return 0;
  int dp[] = new int[A.length];
  //A[i]-A[j]+dp[j-2]
  int max = -A[0];
  for (int i = 1; i < A.length; i++) {
    dp[i] = Math.max(dp[i - 1], A[i] + max);
    if (i - 2 >= 0) {
      max = Math.max(max, dp[i - 2] - A[i]);
    } else {
      max = Math.max(max, -A[i]);
    }
  }
  return dp[A.length - 1];
}

代码总结：

• 与上一题是异曲同工。我们首先把dp 的关系式找出来，然后根据这关系式再进行进一步的优化

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

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

总结

给大家总结了5题的 股票系列 题目到这里就结束了，大家可以从看到我们是如何一步一步分析问题然后优化解题方法的。

我们先用枚举的方式把问题暴力解出来，然后观察看哪些地方是可以进行优化的。

三四题我们还学习了如何对DP进行优化。

DP 就是一种关系的转换，在这转换过程中有时会很复杂，但有时又会有规律。

如果这篇文章对你有所帮助，欢迎点赞留言告诉我，我们下期见！