買賣股票，我總結(jié)了這 3 點經(jīng)驗
本文轉(zhuǎn)載自微信公眾號「碼農(nóng)田小齊」，作者66brother。轉(zhuǎn)載本文請聯(lián)系碼農(nóng)田小齊公眾號。
前言
今天我們來聊聊 Leetcode 的華爾街之狼(The Wolf of Wall Street)系列，也稱股票系列， 在 Leetcode 上有 6 題之多。
本文會通過講解其中的幾道經(jīng)典題目再次探究動態(tài)規(guī)劃的魅力，希望能幫助大家對 DP 有更深入的理解。
這類題目在面試中非常常見，也有很多的變種，比如我就被問過不止要返回 profit，還要返回在哪天交易。
不過萬變不離其宗，把握住買賣的原則，你就是贏家。
1. Best Time to Buy and Sell Stock
給你一組數(shù)組 prices=[7,1,5,3,6,4]。prices[i] 代表在第i天股票的價格。你可以進行買與賣的操作，但你得先買了才能賣。(也就是不能 short)你最多進行一次買與賣的操作，問你能夠賺到的最大收益是多少?從本題的數(shù)據(jù)例子來看，我們?nèi)绻?i=1 天買和在 i=4天賣，我們能夠賺到 p[4]-p[1]=5 的收益。這是我們能夠做到的最大收益，其它的操作都不能賺的比5多。
問題分析 ：
首先如果我們在第 i 天進行買的操作，那么賣的操作一定得發(fā)生在第 i 天之后，也就是 prices[i+1 : n] 里
以 prices=[7,1,5,3,6,4] 作為例子，如果我們在 prices[0] 買，那么賣一定發(fā)生在 prices[1 : 5]。
同理，如果我們在 prices[1] 買，賣一定發(fā)生在 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;
- }
代碼總結(jié)：
- 我們枚舉所有的 (i, j) pair，i 代表買，j 代表賣，并且 i < j，但以上暴力代碼的時間復(fù)雜度是 O(n^2)，我們可不可以做的更好呢?
時空復(fù)雜度：
- 時間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)
方法2：
- 如果我們在第 i 天進行買的操作，那么賣的操作一定還是得發(fā)生在 prices[i+1 : n] 這個定理是不變的。
- 換句話說，對于每個買的操作，prices[i]，我們只需要找到 prices[i+1 : n] 里最大的數(shù)即可。
- 我們可以用一個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;
- }
時空復(fù)雜度：
- 時間復(fù)雜度：O(N)
- 空間復(fù)雜度：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;
- }
時空復(fù)雜度：
- 時間復(fù)雜度：O(N)
- 空間復(fù)雜度：O(1)
2. Best Time to Buy and Sell Stock III
與第一題類似，給你一組數(shù)組 prices=[3,3,5,0,0,3,1,4]。
prices[i] 代表在第 i 天股票的價格，可以進行買賣操作，但得先買了才能賣。
這一次，你最多進行2次買與賣的操作，問你能夠賺到的最大收益是多少?
比如這個例子中，我們在第四天買第六天賣，和在第七天買第八天賣，我們可以得到 (3-0)+(4-1)=6，這是我們能得到的最大收益。
問題分析 ：
這道題升級了一點難度，可以進行兩次的交易，但是只要打好了第一題的基礎(chǔ)，這題也并不會太難的。
我們已經(jīng)通過了第一題學(xué)會了如何計算最多進行一次買賣操作的最大利潤，我們將通過已經(jīng)計算好的一次交易最大利潤去計算兩次的是多少。
假設(shè)我們第一次 賣 發(fā)生在 i，那么我們第一次交易得發(fā)生在 prices[0 : i]， 而我們第二次交易得發(fā)生在 prices[i+1 : n]。
- 對于第一次交易，我們可以像第一題的 方法 3 一樣，我們枚舉每一次賣，我們只需要再找到 prices[i+1 : n] 的一次最大利潤操作即可。
- 對于 prices[i+1 : n] 這一段，我們可以枚舉買，如果買發(fā)生在 prices[i]，那么賣得發(fā)生在 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++) {
- //假設(shè)我們第一次賣發(fā)生在i,買得發(fā)生在prices[0:i-1]
- //第二次操作發(fā)生在prices[i+1 : n]，dp[i+1]表示prices[i+1 : n]這段區(qū)間進行一次操作的最大值
- maxProfit = Math.max(maxProfit, dp[i + 1] + (A[i] - minBuy));
- minBuy = Math.min(minBuy, A[i]);
- }
- return maxProfit;
- }
代碼總結(jié)：
- 我們枚舉第一次的賣發(fā)生在 i，那么第一次操作發(fā)生在prices[0 : i]，而第二次操作發(fā)生在 prices[i+1 : n]。
- 我們可以提前對 prices[i+1 : n] 進行提前處理。
- dp[i] 代表 prices[i : n] 最大利潤的一次交易，我們可以像第一題的題解3一樣去枚舉買
- 再枚舉第一次交易的賣，如果它發(fā)生在 i，我們能得到的最大利潤就是prices[i] - min(prices[0 : i-1]) + dp[i+1]
空間復(fù)雜度和時間復(fù)雜度：
- 時間復(fù)雜度：O(N)
- 空間復(fù)雜度：O(N)
3. Best Time to Buy and Sell Stock with Transaction Fee && Best Time to Buy and Sell Stock II
題意：
同樣還是給你一組數(shù)組代表每一天的股價，這次我們可以進行多次買賣，但是每一次買賣你需要多付一個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]。
現(xiàn)在我們剩下的問題就是如何去計算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是賣的天數(shù)
- dp[i] = dp[i - 1];
- for (int j = i - 1; j >= 0; j--) {//j 是買的天數(shù)，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];
- }
代碼總結(jié)：
- 暴力的dp，我們還會通過仔細(xì)觀察 dp 的關(guān)系轉(zhuǎn)移去進行深一步的優(yōu)化
空間復(fù)雜度和時間復(fù)雜度：
- 時間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(N)
方法2：優(yōu)化DP
我們可以從 dp 的關(guān)系轉(zhuǎn)移中進行優(yōu)化：
從方法1我們可以看出 dp[i]=max(dp[i-1], max(prices[i] - prices[j]-fee + dp[j-1]))，從這轉(zhuǎn)移式中我們可以發(fā)現(xiàn) i 是一個不變量，而 j 是變量。
首先，我們設(shè)dp[i]=dp[i-1]。
我們再仔細(xì)的觀察一下這個式子 prices[i] - prices[j]-fee + dp[j-1]，當(dāng)我們枚舉 i 的時候，我們會發(fā)現(xiàn)prices[i] - fee 是個常數(shù)!
我們?nèi)绻咽阶又匦抡硪幌?，那它就?(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];
- }
代碼總結(jié)：
- DP 其實就是一種關(guān)系(式子)的轉(zhuǎn)化，當(dāng)我們求出他的基本關(guān)系的時候，我們可以看看能不能通過它的關(guān)系進行優(yōu)化
空間復(fù)雜度和時間復(fù)雜度：
- 時間復(fù)雜度：O(N)
- 空間復(fù)雜度：O(N)
4. Best Time to Buy and Sell Stock with Cooldown
題意：
給你一個數(shù)組prices = [1,2,3,0,2]，你可以進行多次交易，但每完成一次交易得有一個cooldown，不能連續(xù)做交易
按照以上的數(shù)據(jù)，如果我們按這樣的操作[buy, sell, cooldown, buy, sell] 我們能夠得到利益 (2 - 1) + (2 - 0) =3，這是我們能夠得到的最大利益
問題分析 ：
如果你會了第三題的解法，你會發(fā)現(xiàn)這題與上一題其實是異曲同工
因為有多次交易的關(guān)系，我們可以像上一題那樣，使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])
和上一題一樣，當(dāng)我們在i 這天時，prices[i] 是個常數(shù)。我們只需要找到最大的 (-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];
- }
代碼總結(jié)：
- 與上一題是異曲同工。我們首先把dp 的關(guān)系式找出來，然后根據(jù)這關(guān)系式再進行進一步的優(yōu)化
空間復(fù)雜度和時間復(fù)雜度：
- 時間復(fù)雜度：O(N)
- 空間復(fù)雜度：O(N)
總結(jié)
今天給大家總結(jié)了5題的 股票系列 題目，大家可以從看到我們是如何一步一步分析問題然后優(yōu)化解題方法的。
我們先用枚舉的方式把問題暴力解出來，然后觀察看哪些地方是可以進行優(yōu)化的。
三四題我們還學(xué)習(xí)了如何對DP進行優(yōu)化。
DP 就是一種關(guān)系的轉(zhuǎn)換，在這轉(zhuǎn)換過程中有時會很復(fù)雜，但有時又會有規(guī)律。
