歡迎訪問我的GitHub

這里分類和匯總了欣宸的全部原創(chuàng)(含配套源碼)：https://github.com/zq2599/blog_demos

關(guān)于《LeetCode買賣股票》系列

• 在LeetCode上，有數(shù)道和買賣股票有關(guān)的題目，覆蓋了簡單、中等、困難，要求都是選擇低價時間買入、高價時間賣出，以求達到利潤最大化
• 這類題型的特點就是：典型的動態(tài)規(guī)劃題型，掌握套路后，越做越開心，就算難度是困難的題目，也能從容面對
• 于是，欣宸將此類題目聚集在一起，集中火力分析和解題，構(gòu)成了《LeetCode買賣股票》系列，在該系列中，欣宸與您一同打好基礎(chǔ)，再將該類型題目逐個攻克，在LeetCode世界中做一回股神

本篇概覽

• 對之前的解題經(jīng)歷做了認(rèn)真回顧后，我這邊決定用第122題《買賣股票的最佳時機 II》作為系列的開篇，原因是此題在所有買賣股票的文章中最為典型：題目具備代表性，同時其他題目中奇怪的約束條件如凍結(jié)期、交易次數(shù)等，在122題中都不存在，寫出的狀態(tài)轉(zhuǎn)移方程可以作為其他題目的參考
• 接下來開始做題吧，先看題目

題目信息

• 題號：122
• 難度：中等
• 描述

1. 給你一個整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。
2. 在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。
3. 返回 你能獲得的 最大 利潤 。

• 示例 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

核心問題分析

• 解題的關(guān)鍵，是搞清楚兩個最核心的問題：

1. 我們要的是什么？
2. 變化有哪些？

第一個問題：我們要的是什么？

• 認(rèn)真審題后，我們要的東西可以這樣描述：第i天股市結(jié)束后手里的最大利潤

第二個問題：有哪些變化？

• 很容易發(fā)現(xiàn)，一共有兩種變化：和行為無關(guān)、和行為有關(guān)

1. 和行為無關(guān)的變化：是時間和股價，只要知道是第幾天，也就知道了股價，所以只要聚焦時間變化即可
2. 和行為有關(guān)的變化：股票持有情況，即持有和不持有

確定dp定義

• 弄清楚上述兩個問題后，dp定義也就呼之欲出了：

1. dp數(shù)組的值就是我們想要的東西
2. dp數(shù)組的維度就是變化，一共有兩個變化，所以一共有兩個維度

• 于是，我們對dp數(shù)組的定義如下圖
  
• 上圖中，i的取值好理解，表示第幾天，至于j，我們規(guī)定它只有兩個值：0和1,0代表不持有股票，1代表持有股票
• 下圖是個例子，很容易理解：第3天股市結(jié)束后，未持有股票時，手里的最大利潤是123元
  

狀態(tài)轉(zhuǎn)移方程分析

• 要想寫出狀態(tài)轉(zhuǎn)移方程，首先要弄明白狀態(tài)是怎么變化的，時間狀態(tài)自不必分析，它是客觀在變化的，我們要弄明白的是另一個狀態(tài)：股票持有狀態(tài)，嚴(yán)格來說要弄清楚兩點：

1. 第i天股市結(jié)束后，如果手里持有股票，這個股票是從哪來的？
2. 第i天股市結(jié)束后，如果手里沒有股票，為什么手里會沒有股票？

• 只要弄清楚上述兩個問題，狀態(tài)轉(zhuǎn)移方程也就出來了，接下來逐個分析

手里持有股票的原因

• 第i天股市結(jié)束后，如果手里持有股票，有兩種可能：

1. 第i天之前持有股票，到了第i天啥也不做，此時：dp[i][1]=dp[i-1][1]
2. 第i天之前不持有股票，在第i天購買了，此時：dp[i][1]=dp[i-1][0]-price[i]，因為購買要花錢，所以用手里的錢減去當(dāng)天股價

• 我們要的是最大利潤，所以應(yīng)該取上述兩種情況的最大值
• 現(xiàn)在可以寫出dp[i][1]的表達式了：dp[i][i]=Math.max(dp[i-1][1], dp[i-1][0]-price[i])
• 一圖勝千言，看過下圖您就一定明白了
  

手里未持有股票的原因

• 接下來繼續(xù)分析，第i天股市結(jié)束后如果手里沒有股票，有兩種可能導(dǎo)致：

1. 第i天之前未持有股票，到了第i天啥也不做，此時：dp[i][0]=dp[i-1][0]
2. 第i天之前持有股票，在第i天賣出，此時：dp[i][0]=dp[i-1][1] + price[i]，因為賣出股票會換來錢，所以這里用手里的錢加上當(dāng)天股價

• 我們要的是最大利潤，所以應(yīng)該取上述兩種情況的最大值
• 現(xiàn)在可以寫出dp[i][0]的表達式了：dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]+price[i])
• 一圖勝千言，看過下圖您就一定明白了
  
• 狀態(tài)轉(zhuǎn)移方程已經(jīng)出來了，接下來按部就班寫好代碼提交即可

編碼

• 有了上面的分析，相信此刻您也能流暢的完成編碼了，參考代碼如下

class Solution {
    public int maxProfit(int[] prices) {

        int[][] dp = new int[prices.length][2];

        // 第0天股市結(jié)束后，如果手里沒有股票，那就是沒有購買過，此時最大利潤只能等于0
        // 初始化為0的代碼可以省去
        // dp[0][0] = 0;

        // 第0天股市結(jié)束后，如果手里有股票，那就是當(dāng)前購買的，此時最大利潤就是負(fù)數(shù)
        dp[0][1] = -prices[0];

        for (int i=1;i<prices.length;i++) {
        	// 第i天股市結(jié)束時，手里沒有股票的原因有兩個：
        	// 1. 之前就沒有股票，第i天啥樣沒做
        	// 2. 之前有股票，第i天賣出
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 第i天股市結(jié)束時，手里有股票的原因有兩個：
        	// 1. 之前就有股票，第i天啥樣沒做
        	// 2. 之前沒有股票，第i天買入
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        // 第i天結(jié)束后，手里不持有股票的最大利潤就是返回值
        return dp[prices.length-1][0];
    }
}

• 提交代碼，如下所示，雖然AC了，但是速度很一般，超過26.27%的提交，顯然還有優(yōu)化空間
  

優(yōu)化

• 回顧上述代碼中，dp[i][0]和dp[i][1]都是通過dp[i-i][0]和dp[i-1][1]計算出來的，如此看來，這個dp二維數(shù)組似乎有些浪費，用下面這四個變量足矣

1. prevWithStock：前一天股市結(jié)束后，手里有股票時的最大利潤
2. prevWithoutStock：前一天股市結(jié)束后，手里沒有股票時的最大利潤
3. currentWithStock：當(dāng)天股市結(jié)束后，手里有股票時的最大利潤
4. currentWithoutStock：當(dāng)天股市結(jié)束后，手里沒有股票時的最大利潤

• 優(yōu)化后的代碼如下

class Solution {
    public int maxProfit(int[] prices) {
        // 第0天股市結(jié)束后，如果手里有股票，那就是當(dāng)前購買的，此時最大利潤就是負(fù)數(shù)
        int prevWithStock = -prices[0];

        // 第0天股市結(jié)束后，如果手里沒有股票，那就是沒有購買過，此時最大利潤只能等于0
        int prevWithoutStock = 0;

        // 當(dāng)天股市結(jié)束后，如果手里有股票時的最大利潤
        int currentWithStock;

        // 當(dāng)天股市結(jié)束后，如果手里沒有股票時的最大利潤
        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天結(jié)束后，手里不持有股票的最大利潤就是返回值
        return currentWithoutStock;
    }
}

• 再次提交，稍微提升了一點
  
• 至此，買賣股票的基本套路，以及狀態(tài)轉(zhuǎn)移方程設(shè)計思路和實現(xiàn)，咱們已經(jīng)學(xué)習(xí)到了，接下來的文章中，都會基于這個思路去設(shè)置狀態(tài)轉(zhuǎn)移方程
• 當(dāng)然了，此刻您應(yīng)該還有個疑問：為何速度的排名如此之低？接下來咱們來看看落后的原因

為啥排名不高？

• 這道題本身也有一些特殊：除了動態(tài)規(guī)劃，貪心算法也能解
• 以prices={1, 2, 3}為例，聰明的您應(yīng)該看出來了，如果1買入，3賣出，得到的利潤等于2，屬于最大利潤
• 題目有個約束：一天不能既買入又賣出，如果跳出這個約束，那就可以做到1買入2賣出，然后2買入3賣出，利潤還是2！
• 至于能不能將3-1轉(zhuǎn)化成(3-2)+(2-1)呢？當(dāng)然可以，減去2再加上2，對原題的結(jié)果毫無影響，卻可以改變代碼流程，如下所示，每當(dāng)買入賣出能賺錢時，就將插件累加起來，這樣的計算中，相比前面的代碼，每次循環(huán)中的計算量明顯減少了

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;
    }
}

• 再次提交，這回超越了百分百
  
• 至此又得出一個結(jié)論：本題用動態(tài)規(guī)劃做并沒有錯，也不是動態(tài)規(guī)劃代碼沒寫好，而是有更高效的貪心算法恰巧也能解決此問題
• 經(jīng)過本篇實戰(zhàn)，相信您對動態(tài)規(guī)劃以及股票買賣問題都有了更深的理解，接下來，繼續(xù)挑戰(zhàn)其他股票買賣問題，在LeetCode世界中向著股神前進

歡迎關(guān)注博客園：程序員欣宸

學(xué)習(xí)路上，你不孤單，欣宸原創(chuàng)一路相伴...文章來源地址http://www.zghlxwxcb.cn/news/detail-699382.html

到了這里，關(guān)于LeetCode買賣股票之一：基本套路(122)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！