### 歡迎訪問我的GitHub > 這裡分類和彙總了欣宸的全部原創(含配套源碼)：[https://github.com/zq2599/blog_demos](https://github.com/zq2599/blog_demos) ### 關於《LeetCode買賣股票》系列 - 在LeetC ...
歡迎訪問我的GitHub
這裡分類和彙總了欣宸的全部原創(含配套源碼)：https://github.com/zq2599/blog_demos
關於《LeetCode買賣股票》系列
- 在LeetCode上，有數道和買賣股票有關的題目，覆蓋了簡單、中等、困難，要求都是選擇低價時間買入、高價時間賣出，以求達到利潤最大化
- 這類題型的特點就是：典型的動態規劃題型，掌握套路後，越做越開心，就算難度是困難的題目，也能從容面對
- 於是，欣宸將此類題目聚集在一起，集中火力分析和解題，構成了《LeetCode買賣股票》系列，在該系列中，欣宸與您一同打好基礎，再將該類型題目逐個攻剋，在LeetCode世界中做一回股神
本篇概覽
- 對之前的解題經歷做了認真回顧後，我這邊決定用第122題《買賣股票的最佳時機 II》作為系列的開篇，原因是此題在所有買賣股票的文章中最為典型：題目具備代表性，同時其他題目中奇怪的約束條件如凍結期、交易次數等，在122題中都不存在，寫出的狀態轉移方程可以作為其他題目的參考
- 接下來開始做題吧，先看題目
題目信息
- 題號：122
- 難度：中等
- 描述
- 給你一個整數數組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。
- 在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然後在 同一天 出售。
- 返回 你能獲得的 最大 利潤 。
- 示例 1：
輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。
隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3 。
總利潤為 4 + 3 = 7 。
- 示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。
總利潤為 4 。
- 示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 交易無法獲得正利潤，所以不參與交易可以獲得最大利潤，最大利潤為 0 。
- 提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104
核心問題分析
- 解題的關鍵，是搞清楚兩個最核心的問題：
- 我們要的是什麼？
- 變化有哪些？
第一個問題：我們要的是什麼？
- 認真審題後，我們要的東西可以這樣描述：第i天股市結束後手裡的最大利潤
第二個問題：有哪些變化？
- 很容易發現，一共有兩種變化：和行為無關、和行為有關
- 和行為無關的變化：是時間和股價，只要知道是第幾天，也就知道了股價，所以只要聚焦時間變化即可
- 和行為有關的變化：股票持有情況，即持有和不持有
確定dp定義
- 弄清楚上述兩個問題後，dp定義也就呼之欲出了：
- dp數組的值就是我們想要的東西
- dp數組的維度就是變化，一共有兩個變化，所以一共有兩個維度
- 於是，我們對dp數組的定義如下圖
- 上圖中，i的取值好理解，表示第幾天，至於j，我們規定它只有兩個值：0和1,0代表不持有股票，1代表持有股票
- 下圖是個例子，很容易理解：第3天股市結束後，未持有股票時，手裡的最大利潤是123元
狀態轉移方程分析
- 要想寫出狀態轉移方程，首先要弄明白狀態是怎麼變化的，時間狀態自不必分析，它是客觀在變化的，我們要弄明白的是另一個狀態：股票持有狀態，嚴格來說要弄清楚兩點：
- 第i天股市結束後，如果手裡持有股票，這個股票是從哪來的？
- 第i天股市結束後，如果手裡沒有股票，為什麼手裡會沒有股票？
- 只要弄清楚上述兩個問題，狀態轉移方程也就出來了，接下來逐個分析
手裡持有股票的原因
- 第i天股市結束後，如果手裡持有股票，有兩種可能：
- 第i天之前持有股票，到了第i天啥也不做，此時：dp[i][1]=dp[i-1][1]
- 第i天之前不持有股票，在第i天購買了，此時：dp[i][1]=dp[i-1][0]-price[i]，因為購買要花錢，所以用手裡的錢減去當天股價
- 我們要的是最大利潤，所以應該取上述兩種情況的最大值
- 現在可以寫出dp[i][1]的表達式了：dp[i][i]=Math.max(dp[i-1][1], dp[i-1][0]-price[i])
- 一圖勝千言，看過下圖您就一定明白了
手裡未持有股票的原因
- 接下來繼續分析，第i天股市結束後如果手裡沒有股票，有兩種可能導致：
- 第i天之前未持有股票，到了第i天啥也不做，此時：dp[i][0]=dp[i-1][0]
- 第i天之前持有股票，在第i天賣出，此時：dp[i][0]=dp[i-1][1] + price[i]，因為賣出股票會換來錢，所以這裡用手裡的錢加上當天股價
- 我們要的是最大利潤，所以應該取上述兩種情況的最大值
- 現在可以寫出dp[i][0]的表達式了：dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+price[i])
- 一圖勝千言，看過下圖您就一定明白了
- 狀態轉移方程已經出來了，接下來按部就班寫好代碼提交即可
編碼
- 有了上面的分析，相信此刻您也能流暢的完成編碼了，參考代碼如下
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
// 第0天股市結束後，如果手裡沒有股票，那就是沒有購買過，此時最大利潤只能等於0
// 初始化為0的代碼可以省去
// dp[0][0] = 0;
// 第0天股市結束後，如果手裡有股票，那就是當前購買的，此時最大利潤就是負數
dp[0][1] = -prices[0];
for (int i=1;i<prices.length;i++) {
// 第i天股市結束時，手裡沒有股票的原因有兩個：
// 1. 之前就沒有股票，第i天啥樣沒做
// 2. 之前有股票，第i天賣出
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
// 第i天股市結束時，手裡有股票的原因有兩個：
// 1. 之前就有股票，第i天啥樣沒做
// 2. 之前沒有股票，第i天買入
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
// 第i天結束後，手裡不持有股票的最大利潤就是返回值
return dp[prices.length-1][0];
}
}
- 提交代碼，如下所示，雖然AC了，但是速度很一般，超過26.27%的提交，顯然還有優化空間
優化
- 回顧上述代碼中，dp[i][0]和dp[i][1]都是通過dp[i-i][0]和dp[i-1][1]計算出來的，如此看來，這個dp二維數組似乎有些浪費，用下麵這四個變數足矣
- prevWithStock：前一天股市結束後，手裡有股票時的最大利潤
- prevWithoutStock：前一天股市結束後，手裡沒有股票時的最大利潤
- currentWithStock：當天股市結束後，手裡有股票時的最大利潤
- currentWithoutStock：當天股市結束後，手裡沒有股票時的最大利潤
- 優化後的代碼如下
class Solution {
public int maxProfit(int[] prices) {
// 第0天股市結束後，如果手裡有股票，那就是當前購買的，此時最大利潤就是負數
int prevWithStock = -prices[0];
// 第0天股市結束後，如果手裡沒有股票，那就是沒有購買過，此時最大利潤只能等於0
int prevWithoutStock = 0;
// 當天股市結束後，如果手裡有股票時的最大利潤
int currentWithStock;
// 當天股市結束後，如果手裡沒有股票時的最大利潤
int currentWithoutStock = 0;
for (int i=1;i<prices.length;i++) {
currentWithoutStock = Math.max(prevWithoutStock, prevWithStock + prices[i]);
currentWithStock = Math.max(prevWithStock, prevWithoutStock - prices[i]);
prevWithStock = currentWithStock;
prevWithoutStock = currentWithoutStock;
}
// 第i天結束後，手裡不持有股票的最大利潤就是返回值
return currentWithoutStock;
}
}
- 再次提交，稍微提升了一點
- 至此，買賣股票的基本套路，以及狀態轉移方程設計思路和實現，咱們已經學習到了，接下來的文章中，都會基於這個思路去設置狀態轉移方程
- 當然了，此刻您應該還有個疑問：為何速度的排名如此之低？接下來咱們來看看落後的原因
為啥排名不高？
- 這道題本身也有一些特殊：除了動態規劃，貪心演算法也能解
- 以prices={1, 2, 3}為例，聰明的您應該看出來了，如果1買入，3賣出，得到的利潤等於2，屬於最大利潤
- 題目有個約束：一天不能既買入又賣出，如果跳出這個約束，那就可以做到1買入2賣出，然後2買入3賣出，利潤還是2！
- 至於能不能將3-1轉化成(3-2)+(2-1)呢？當然可以，減去2再加上2，對原題的結果毫無影響，卻可以改變代碼流程，如下所示，每當買入賣出能賺錢時，就將插件累加起來，這樣的計算中，相比前面的代碼，每次迴圈中的計算量明顯減少了
class Solution {
public int maxProfit(int[] prices) {
if (prices.length<2) {
return 0;
}
int total = 0;
for (int i=1;i<prices.length;i++) {
if (prices[i]>prices[i-1]) {
total += prices[i] - prices[i-1];
}
}
return total;
}
}
- 再次提交，這回超越了百分百
- 至此又得出一個結論：本題用動態規劃做並沒有錯，也不是動態規劃代碼沒寫好，而是有更高效的貪心演算法恰巧也能解決此問題
- 經過本篇實戰，相信您對動態規劃以及股票買賣問題都有了更深的理解，接下來，繼續挑戰其他股票買賣問題，在LeetCode世界中向著股神前進
