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