LeetCode 股票买卖问题
LeetCode 股票買賣問題
文章目錄
- LeetCode 股票買賣問題
- 一、問題描述
- **二、 窮舉框架**
- **三、 狀態轉移框架**
- **四、解題**
- `第一題`：`K = 1`
- `第?題`， `k = +infinity`
- `第三題`， `k = +infinity with cooldown`
- `第四題`， `k = +infinity with fee`
- `第五題`， `k = 2`
- `第六題`， `k = any integer`
- **五、 最后總結**
一、問題描述
給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。示例 1:
輸入: [2,4,1], k = 2 輸出: 2 解釋: 在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。示例 2:
輸入: [3,2,6,5,0,3], k = 2 輸出: 7 解釋: 在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。開始先不進行該題的解答，我們先分析整個框架，拿這道題來舉例，最后解決leetcode上所有的股票買賣問題
二、 窮舉框架
我們不?遞歸思想進?窮舉， ?是利?「狀態」 進?窮舉。 我們具體到每?天， 看看總共有?種可能的「狀態」 ， 再找出每個「狀態」 對應的「選擇」 。 我們要窮舉所有「狀態」 ， 窮舉的?的是根據對應的「選擇」 更新狀態。 聽起來抽象， 你只要記住「狀態」 和「選擇」 兩個詞就?， 下?實操?下就很容易明?了。
for 狀態1 in 狀態1的所有取值：for 狀態2 in 狀態2的所有取值：for ...dp[狀態1][狀態2][...] = 擇優(選擇1， 選擇2...)?如某個股票個問題， 每天都有三種「選擇」 ： 買?、 賣出、 ?操作， 我們?
buy, sell, rest 表?這三種選擇。 但問題是， 并不是每天都可以任意選擇這三
種選擇的， 因為 sell 必須在 buy 之后， buy 必須在 sell 之后。 那么 rest 操作
還應該分兩種狀態， ?種是 buy 之后的 rest（持有了股票） ， ?種是 sell 之
后的 rest（沒有持有股票） 。 ?且別忘了， 我們還有交易次數 k 的限制， 就
是說你 buy 還只能在 k > 0 的前提下操作。
很復雜對吧， 不要怕， 我們現在的?的只是窮舉， 你有再多的狀態， ?夫要做的就是?把梭全部列舉出來。 這個問題的「狀態」 有三個， 第?個是天數， 第?個是允許交易的最?次數， 第三個是當前的持有狀態（即之前說的rest 的狀態， 我們不妨? 1 表?持有， 0 表?沒有持有） 。 然后我們??個三維數組就可以裝下這?種狀態的全部組合：
dp[i][k][0 or 1] 0 <= i <= n-1, 1 <= k <= K n 為天數， ? K 為最多交易數 此問題共 n × K × 2 種狀態， 全部窮舉就能搞定。 for 0 <= i < n:for 1 <= k <= K:for s in {0, 1}:dp[i][k][s] = max(buy, sell, rest)簡單解釋一下每?個狀態的含義， ?如說 dp[3][2][1]的含義就是： 今天是第三天， 我現在?上持有著股票， ?今最多進? 2 次交易。 再?如 dp[2][3][0] 的含義： 今天是第?天， 我現在?上沒有持有股票， ?今最多進? 3 次交易。 很容易理解， 對吧？
我們想求的最終答案是 dp[n - 1][K][0]， 即最后?天， 最多允許 K 次交易，最多獲得多少利潤。 讀者可能問為什么不是 dp[n - 1][K][1]？ 因為 [1] 代表?上還持有股票， [0] 表??上的股票已經賣出去了， 很顯然后者得到的利潤?定?于前者
三、 狀態轉移框架
現在， 我們完成了「狀態」 的窮舉， 我們開始思考每種「狀態」 有哪些「選
擇」 ， 應該如何更新「狀態」 。 只看「持有狀態」 ， 可以畫個狀態轉移圖
通過這個圖可以很清楚地看到， 每種狀態（0 和 1） 是如何轉移?來的。 根
據這個圖， 我們來寫?下狀態轉移?程：
這個解釋應該很清楚了， 如果 buy， 就要從利潤中減去 prices[i]， 如果 sell，
就要給利潤增加 prices[i]。 今天的最?利潤就是這兩種可能選擇中較?的那
個。 ?且注意 k 的限制， 我們在選擇 buy 的時候， 把 k 減?了 1， 很好理解
吧， 當然你也可以在 sell 的時候減 1， ?樣的。
現在， 我們已經完成了動態規劃中最困難的?步： 狀態轉移?程。 如果之前
的內容你都可以理解， 那么你已經可以秒殺所有問題了， 只要套這個框架就
?了。 不過還差最后?點點， 就是定義 base case， 即最簡單的情況。
把上?的狀態轉移?程總結?下：
base case： dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -infinity狀態轉移?程： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])讀者可能會問， 這個數組索引是 -1 怎么編程表?出來呢， 負?窮怎么表?
呢？ 這都是細節問題， 有很多?法實現
四、解題
第一題：K = 1
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能獲取的最大利潤。
注意你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4] 輸出: 5 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。 示例 2:輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。直接套狀態轉移?程， 根據 base case， 可以做?些化簡：
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]) dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) = max(dp[i-1][1][1], -prices[i])解釋： k = 0 的 base case， 所以 dp[i-1][0][0] = 0。 現在發現 k 都是 1， 不會改變， 即 k 對狀態轉移已經沒有影響了。 可以進?進?步化簡去掉所有 k：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], -prices[i])完整代碼：
int n = prices.length; int[][] dp = new int[n][2]; for (int i = 0; i < n; i++) {dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = Math.max(dp[i-1][1], -prices[i]); } return dp[n - 1][0];顯然 i = 0 時 dp[i-1] 是不合法的。 這是因為我們沒有對 i 的 base case 進?處
理。 可以這樣處理：
C++代碼
class Solution { public:int maxProfit(vector<int>& prices) {if(prices.empty()){return 0;}//定義一個二維數組，根據博客當中的講解，dp[i][j]就代表第i天在j狀態下的最大利潤vector<vector<int>> dp(prices.size(),vector<int>(2,0));//循環遍歷for(int i = 0;i < prices.size();i++){if(i - 1 < 0){//-infinity用來標記不可能存在的情況，代表負無窮dp[i][0] = 0;// 解釋：//dp[i][0]// = max(dp[-1][0], dp[-1][1] + prices[i])// = max(0, -infinity + prices[i]) = 0dp[i][1] = -prices[i];//解釋：// dp[i][1]// = max(dp[-1][1], dp[-1][0] - prices[i])// = max(-infinity, 0 - prices[i])// = -prices[i]continue;}//詳細在博客中有介紹，這里就不解釋了dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1],- prices[i]);}//注意最后返回的是dp[prices.size() - 1][0]，而不是dp[prices.size() - 1][1]//因為后者還持有沒有賣出去，其利潤肯定比前者小return dp[prices.size() - 1][0];} };第?題就解決了， 但是這樣處理 base case 很?煩， ?且注意?下狀態轉移
?程， 新狀態只和相鄰的?個狀態有關， 其實不?整個 dp 數組， 只需要?
個變量儲存相鄰的那個狀態就?夠了， 這樣可以把空間復雜度降到 O(1):
第?題， k = +infinity
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4] 輸出: 7 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。示例 2:
輸入: [1,2,3,4,5] 輸出: 4 解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。示例 3:
輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。如果 k 為正?窮， 那么就可以認為 k 和 k - 1 是?樣的。 可以這樣改寫框
架：
完整代碼：
int maxProfit_k_inf(int[] prices) {int n = prices.length;int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {int temp = dp_i_0;dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);dp_i_1 = Math.max(dp_i_1, temp - prices[i]);} return dp_i_0; }C++代碼
class Solution { public:int maxProfit(vector<int>& prices) {if(prices.empty()){return 0;}// 博客中有詳細解釋，就不注釋了int dp_i_0 = 0;int dp_i_1 = INT_MIN;for(int i = 0;i < prices.size();i++){dp_i_0 = max(dp_i_0 , dp_i_1 + prices[i]);dp_i_1 = max(dp_i_1,dp_i_0 - prices[i]);}return dp_i_0;} };第三題， k = +infinity with cooldown
給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格 。?
設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:
每次 sell 之后要等?天才能繼續交易。 只要把這個特點融?上?題的狀態轉
移?程即可：
完整代碼：
int maxProfit_with_cool(int[] prices) {int n = prices.length;int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;int dp_pre_0 = 0; // 代表 dp[i-2][0]for (int i = 0; i < n; i++) {int temp = dp_i_0;dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);dp_pre_0 = temp;} return dp_i_0; }C++代碼：
class Solution { public:int maxProfit(vector<int>& prices) {int n = prices.size();if(n == 0){return 0;}int dp_i_0 = 0;int dp_i_1 = INT_MIN;int dp_pre_0 = 0; // 代表 dp[i-2][0]for (int i = 0; i < n; i++) {int temp = dp_i_0;dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i]);dp_pre_0 = temp;} return dp_i_0;} };第四題， k = +infinity with fee
給定一個整數數組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負整數 fee 代表了交易股票的手續費用。
你可以無限次地完成交易，但是你每次交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。
返回獲得利潤的最大值。
示例 1:
輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2 輸出: 8 解釋: 能夠達到的最大利潤: 在此處買入 prices[0] = 1 在此處賣出 prices[3] = 8 在此處買入 prices[4] = 4 在此處賣出 prices[5] = 9 總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.每次交易要?付?續費， 只要把?續費從利潤中減去即可。 改寫?程：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee) 解釋： 相當于買?股票的價格升?了。 在第?個式??減也是?樣的， 相當于賣出股票的價格減?了。完整代碼：
int maxProfit_with_fee(int[] prices, int fee) {int n = prices.length;int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {int temp = dp_i_0;dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);} return dp_i_0; }C++代碼：
class Solution { public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();if(n == 0){return 0;}int dp_i_0 = 0, dp_i_1 = INT_MIN;for (int i = 0; i < n; i++) {int temp = dp_i_0;//需要用一個臨時變量來保存dp_i_0的值，因為在計算第i天的時候，dp_i_0//已經發生改變dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);dp_i_1 = max(dp_i_1, temp - prices[i] - fee);} return dp_i_0;} };第五題， k = 2
給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [3,3,5,0,0,3,1,4] 輸出: 6 解釋: 在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。隨后，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。示例 2:
輸入: [1,2,3,4,5] 輸出: 4 解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。 因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。示例 3:
輸入: [7,6,4,3,1] 輸出: 0 解釋: 在這個情況下, 沒有交易完成, 所以最大利潤為 0。k = 2 和前?題?的情況稍微不同， 因為上?的情況都和 k 的關系不太?。要么 k 是正?窮， 狀態轉移和 k 沒關系了； 要么 k = 1， 跟 k = 0 這個 base case 挨得近， 最后也沒有存在感。
這道題 k = 2 和后?要講的 k 是任意正整數的情況中， 對 k 的處理就凸顯出來了。 我們直接寫代碼， 邊寫邊分析原因。
原始的動態轉移?程， 沒有可化簡的地? dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])按照之前的代碼， 我們可能想當然這樣寫代碼（錯誤的） ：
int k = 2; int[][][] dp = new int[n][k + 1][2]; for (int i = 0; i < n; i++)if (i - 1 == -1) { /* 處理?下 base case*/ }dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); } return dp[n - 1][k][0];為什么錯誤？ 我這不是照著狀態轉移?程寫的嗎？
這道題由于沒有消掉 k 的影響， 所以必須要對 k 進?窮舉：
int max_k = 2; int[][][] dp = new int[n][max_k + 1][2];for (int i = 0; i < n; i++) {for (int k = max_k; k >= 1; k--) {if (i - 1 == -1) { /*處理 base case */ }dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);}} // 窮舉了 n × max_k × 2 個狀態， 正確。 return dp[n - 1][max_k][0];C++代碼：
class Solution { public:int maxProfit(vector<int>& prices) {if(prices.empty()){return 0;}int max_k = 2;vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(max_k + 1,vector<int>(2,0)));//循環遍歷for(int i = 0;i < prices.size();i++){for(int k = max_k;k >= 1;k--){if(i - 1 < 0){dp[i][k][0] = 0;dp[i][k][1] = -prices[i];continue;}dp[i][k][0] = max(dp[i - 1][k][0],dp[i - 1][k][1] + prices[i]);dp[i][k][1] = max(dp[i - 1][k][1],dp[i - 1][k - 1][0]- prices[i]);}}return dp[prices.size() - 1][max_k][0];} };第六題， k = any integer
給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。
注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [2,4,1], k = 2 輸出: 2 解釋: 在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。示例 2:
輸入: [3,2,6,5,0,3], k = 2 輸出: 7 解釋: 在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 。隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。有了上?題 k = 2 的鋪墊， 這題應該和上?題的第?個解法沒啥區別。 但是出現了?個超內存的錯誤， 原來是傳?的 k 值會?常?， dp 數組太?了。現在想想， 交易次數 k 最多有多?呢？?次交易由買?和賣出構成， ?少需要兩天。 所以說有效的限制 k 應該不超過 n/2， 如果超過， 就沒有約束作?了， 相當于 k = +infinity。 這種情況是之前解決過的
int maxProfit_k_any(int max_k, int[] prices) {int n = prices.length;if (max_k > n / 2)return maxProfit_k_inf(prices);int[][][] dp = new int[n][max_k + 1][2];for (int i = 0; i < n; i++)for (int k = max_k; k >= 1; k--) {if (i - 1 == -1) { /* 處理 base case */ }dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i ]);dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices [i]);}return dp[n - 1][max_k][0]; }C++代碼（為了不重復換個寫法）
class Solution { public:int maxProfit(int k, vector<int>& prices) {if (prices.size() < 2 || k < 1) return 0;int N = prices.size();if (k >= N / 2) {int res = 0;for (int i = 1; i < N; ++i) {if (prices[i] > prices[i - 1]) {res += prices[i] - prices[i - 1];}}return res;}vector<vector<int> > dp(k + 1, vector<int>{0, INT_MIN});for (int i = 0; i < N; ++i) {for (int j = k; j > 0; --j) {dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);}}return dp[k][0];} };五、 最后總結
本?給?家講了如何通過狀態轉移的?法解決復雜的問題， ??個狀態轉移?程秒殺了 6 道股票買賣問題， 現在想想， 其實也不算難對吧？ 這已經屬于動態規劃問題中較困難的了。
關鍵就在于列舉出所有可能的「狀態」 ， 然后想想怎么窮舉更新這些「狀
態」 。 ?般??個多維 dp 數組儲存這些狀態， 從 base case 開始向后推進，
推進到最后的狀態， 就是我們想要的答案。 想想這個過程， 你是不是有點理
解「動態規劃」 這個名詞的意義了呢？
具體到股票買賣問題， 我們發現了三個狀態， 使?了?個三維數組， ??還是窮舉 + 更新， 不過我們可以說的??上?點， 這叫「三維 DP」 ， 怕不怕？
總結
以上是生活随笔為你收集整理的LeetCode 股票买卖问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 动态规划之KMP字符匹配算法
- 下一篇： LeetCode 打家劫舍问题