買賣股票，我總結了這 3 點經驗
本文轉載自微信公眾號「碼農田小齊」，作者66brother。轉載本文請聯系碼農田小齊公眾號。
前言
今天我們來聊聊 Leetcode 的華爾街之狼(The Wolf of Wall Street)系列，也稱股票系列， 在 Leetcode 上有 6 題之多。
本文會通過講解其中的幾道經典題目再次探究動態規劃的魅力，希望能幫助大家對 DP 有更深入的理解。
這類題目在面試中非常常見，也有很多的變種，比如我就被問過不止要返回 profit，還要返回在哪天交易。
不過萬變不離其宗，把握住買賣的原則，你就是贏家。
1. Best Time to Buy and Sell Stock
給你一組數組 prices=[7,1,5,3,6,4]。prices[i] 代表在第i天股票的價格。你可以進行買與賣的操作，但你得先買了才能賣。(也就是不能 short)你最多進行一次買與賣的操作，問你能夠賺到的最大收益是多少?從本題的數據例子來看，我們如果在 i=1 天買和在 i=4天賣，我們能夠賺到 p[4]-p[1]=5 的收益。這是我們能夠做到的最大收益，其它的操作都不能賺的比5多。
問題分析 ：
首先如果我們在第 i 天進行買的操作，那么賣的操作一定得發生在第 i 天之后，也就是 prices[i+1 : n] 里
以 prices=[7,1,5,3,6,4] 作為例子，如果我們在 prices[0] 買，那么賣一定發生在 prices[1 : 5]。
同理，如果我們在 prices[1] 買，賣一定發生在 prices[2 : 5]。
我們可以把所有的 (買，賣) pair 生成出來然后找到收益性最高的那對即可。
方法1 ：暴力枚舉
- public int maxProfit(int[] prices) {
- int maxProfit = 0; //我們可以不進行操作，所以初始是 0 而不是 INT_MIN
- for(int i = 0; i < prices.length; i++){
- //在 i 天 進行購買
- for(int j = i + 1; j < prices.length; j++){
- //在 j 天進行出售
- int profit = prices[j] - prices[i];
- maxProfit = Math.max(maxProfit, profit);
- }
- }
- return maxProfit;
- }
代碼總結：
- 我們枚舉所有的 (i, j) pair，i 代表買，j 代表賣，并且 i < j，但以上暴力代碼的時間復雜度是 O(n^2)，我們可不可以做的更好呢?
時空復雜度：
- 時間復雜度：O(N^2)
- 空間復雜度：O(1)
方法2：
- 如果我們在第 i 天進行買的操作，那么賣的操作一定還是得發生在 prices[i+1 : n] 這個定理是不變的。
- 換句話說，對于每個買的操作，prices[i]，我們只需要找到 prices[i+1 : n] 里最大的數即可。
- 我們可以用一個dp array 去記錄，dp[i] 表示 max(prices[i : n]) 。
- 如果我們在 i 這天進行買的操作，獲得的最大的收益就是 dp[i+1] - prices[i] (這里我們要注意outbound)
- public int maxProfit(int[] prices) {
- int maxProfit = 0;
- int n = prices.length;
- int dp[] = new int[n];
- dp[n - 1] = prices[n - 1];
- for (int i = n - 2; i >= 0; i--) {
- dp[i] = Math.max(prices[i], dp[i + 1]);
- }
- for (int i = 0; i < n - 1; i++) {
- maxProfit = Math.max(maxProfit, dp[i + 1] - prices[i]);
- }
- return maxProfit;
- }
時空復雜度：
- 時間復雜度：O(N)
- 空間復雜度：O(N)
方法3：
我們其實可以把空間壓縮到 O(1)，比起使用一個dp array 去記錄，我們可以直接一邊走一邊記錄。
- public int maxProfit(int[] prices) {
- int n = prices.length;
- int maxSell = prices[n - 1];
- int maxProfit = 0;
- for (int i = n - 2; i >= 0; i--) {
- maxProfit = Math.max(maxProfit, maxSell - prices[i]);
- maxSell = Math.max(maxSell, prices[i]);
- }
- return maxProfit;
- }
時空復雜度：
- 時間復雜度：O(N)
- 空間復雜度：O(1)
2. Best Time to Buy and Sell Stock III
與第一題類似，給你一組數組 prices=[3,3,5,0,0,3,1,4]。
prices[i] 代表在第 i 天股票的價格，可以進行買賣操作，但得先買了才能賣。
這一次，你最多進行2次買與賣的操作，問你能夠賺到的最大收益是多少?
比如這個例子中，我們在第四天買第六天賣，和在第七天買第八天賣，我們可以得到 (3-0)+(4-1)=6，這是我們能得到的最大收益。
問題分析 ：
這道題升級了一點難度，可以進行兩次的交易，但是只要打好了第一題的基礎，這題也并不會太難的。
我們已經通過了第一題學會了如何計算最多進行一次買賣操作的最大利潤，我們將通過已經計算好的一次交易最大利潤去計算兩次的是多少。
假設我們第一次 賣 發生在 i，那么我們第一次交易得發生在 prices[0 : i]， 而我們第二次交易得發生在 prices[i+1 : n]。
- 對于第一次交易，我們可以像第一題的 方法 3 一樣，我們枚舉每一次賣，我們只需要再找到 prices[i+1 : n] 的一次最大利潤操作即可。
- 對于 prices[i+1 : n] 這一段，我們可以枚舉買，如果買發生在 prices[i]，那么賣得發生在 prices[i+1 : n]。
方法1：
- public int maxProfit(int[] A) {
- int n = A.length;
- int maxProfit = 0;
- //dp[i] 代表 prices[i:n] 能得到的最大一次交易利潤，也就是我們的第二次操作。
- int dp[] = new int[n];
- int maxSell = A[n-1];
- for (int i = n - 2; i >= 0; i--) {
- //maxSell-A[i] 代表如果我們在i這天進行購買的話的最大利潤
- dp[i] = Math.max(dp[i+1], maxSell - A[i]);
- maxSell = Math.max(maxSell, A[i]);
- maxProfit = Math.max(maxProfit, dp[i]);
- }
- int minBuy = A[0];
- for (int i = 1; i < A.length - 1; i++) {
- //假設我們第一次賣發生在i,買得發生在prices[0:i-1]
- //第二次操作發生在prices[i+1 : n]，dp[i+1]表示prices[i+1 : n]這段區間進行一次操作的最大值
- maxProfit = Math.max(maxProfit, dp[i + 1] + (A[i] - minBuy));
- minBuy = Math.min(minBuy, A[i]);
- }
- return maxProfit;
- }
代碼總結：
- 我們枚舉第一次的賣發生在 i，那么第一次操作發生在prices[0 : i]，而第二次操作發生在 prices[i+1 : n]。
- 我們可以提前對 prices[i+1 : n] 進行提前處理。
- dp[i] 代表 prices[i : n] 最大利潤的一次交易，我們可以像第一題的題解3一樣去枚舉買
- 再枚舉第一次交易的賣，如果它發生在 i，我們能得到的最大利潤就是prices[i] - min(prices[0 : i-1]) + dp[i+1]
空間復雜度和時間復雜度：
- 時間復雜度：O(N)
- 空間復雜度：O(N)
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
我們試著像第一題的方法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)
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 就是一種關系的轉換，在這轉換過程中有時會很復雜，但有時又會有規律。
