本期，我將給大家講解的是有關(guān)動態(tài)規(guī)劃類的題——買賣股票的最佳時機。這個系列總共有四道題。接下來，讓我們一起去看看！??！

目錄

（一）買賣股票的最佳時機

（二）買賣股票的最佳時機 II

（三）買賣股票的最佳時機 III

（四）買賣股票的最佳時機 IV

（一）買賣股票的最佳時機

LeetCode題目鏈接：買賣股票的最佳時機

題目如下：

?

題目分析：

第一題，我們先來看最簡單的（題目的難度也是逐級提升的）。

• 思路一：

首先，我們有的小伙伴一讀題，最先想到的可能就是暴力去求解這道題目，但是很遺憾當(dāng)我們提交代碼的時候顯示的是代碼超時了。因此，很顯然暴力解法顯然不是出題者要考察我們的地方。

• 思路二：

那么暴力求解不行，還有沒有其他思路呢？我們通過分析題目，主要意思就是找到最多一次買賣股票可以獲得的最大利潤的問題的解決方案。我們可以利用貪心的思路來分析，主要原理是跟蹤到目前為止看到的最低價格和以當(dāng)前價格賣出可以獲得的最大利潤，通過迭代價格并相應(yīng)地更新這些值，我們可以找到可以獲得的最大利潤。

• 思路三：

那么除了上述的貪心去求解還有沒有其他思路呢？其實還有一種我們今天主要講的動態(tài)規(guī)劃算法。

解題思路：

在這里，我只給出動態(tài)規(guī)劃的具體實現(xiàn)過程。

• step1：確定【arry】數(shù)組以及下標(biāo)的含義

首先，我們初始化一個二維數(shù)組 arry，其中大小是價格向量的大?。╯ize為給出的數(shù)組?prices 的大小），arry 中每行的第一個元素表示買入或者賣出的天數(shù)，第二個元素表示當(dāng)天的狀態(tài)。

arry[i][0]：

• 表示第i天持有股票所得最多現(xiàn)金 。因為剛開始時沒錢買，所以開始現(xiàn)金是0，因此第i天買入股票現(xiàn)金就是 -prices[i]， 這是一個負數(shù)；
• arry[0][0]表示第0天持有股票，此時的持有股票就一定是買入股票了，因為不可能有前一天推出來，所以arry[0][0] -= prices[0];

arry[i][1]：

• 表示第i天不持有股票所得最多現(xiàn)金，即也許是一直都還沒有沒有買入，或者要賣出；
• arry[0][1]表示第0天不持有股票，不持有股票那么現(xiàn)金就是0，所以arry[0][1] = 0;

• step2：確定遞推公式

如果第i天持有股票即arry[i][0]， 那么遞歸公式可以像如下這樣：

• 如果在當(dāng)前前的前一天即（ i-1）?天就持有股票的話，那么當(dāng)前所持有的現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：arry[i - 1][0]
• 如果是在當(dāng)前這一天買入股票即（i），那么此時所持有的就是買入今天的股票后所得現(xiàn)金即：-prices[i]（為負數(shù)）

???arry[i][0] = max(arry[i - 1][0], -prices[i])

如果第i天不持有股票即arry[i][1]， 那么遞歸公式可以像如下這樣：

• 如果在第（i-1）天未持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 即：arry[i - 1][1]
• 如果在第（ i ）天賣出股票，所得現(xiàn)金就是按照今天股票價格賣出后所得現(xiàn)金即：prices[i] + arry[i - 1][0]

???arry[i][1] = max(arry[i - 1][1], prices[i] + arry[i - 1][0])

• step3：確定遍歷順序

從遞推公式可以看出arry[i]都是由arry[i - 1]推導(dǎo)出來的，因此是從前向后遍歷

• step4：圖解展示

?

?

代碼展示：

• 暴力解法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    int n = (int)prices.size()；
    int res = 0;
        for (int i = 0; i < n; ++i){
            for (int j = i + 1; j < n; ++j) {
                res = max(res, prices[j] - prices[i]);
            }
        }
        return res;
   }
};

性能分析：

• 時間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)

• 貪心算法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int num = INT_MAX;
        int res = 0;
        for (int i = 0; i < prices.size(); i++) {
            num = min(num, prices[i]); 
            res = max(res, prices[i] - num); 
        }
        return res;
    }
};

性能分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

• 動態(tài)規(guī)劃：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        if (size == 0) 
            return 0;
        vector<vector<int>> arry(size, vector<int>(2));
        arry[0][0] -= prices[0];
        arry[0][1] = 0;
        for (int i = 1; i < size; i++) {
            arry[i][0] = max(arry[i - 1][0], -prices[i]);
            arry[i][1] = max(arry[i - 1][1], prices[i] + arry[i - 1][0]);
        }
        return arry[size - 1][1];

    }
};

?性能分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

（二）買賣股票的最佳時機 II

LeetCode題目鏈接：買賣股票的最佳時機 II

題目如下：

?

題目分析：

大家通過分析這道題，我們可以發(fā)現(xiàn)這道題跟上道題目的差別就在于本題股票可以進行多次的買賣操作（注意只有一只股票，所以再次購買前要出售掉之前的股票）。

• 思路一：

小伙伴們看到這道題目想的就是 --?選一個低的買入，再選個高的賣，再選一個低的買入.....循環(huán)反復(fù)。

其實，我們對這種思路進行分解 --?只收集正利潤，即最終的最大利潤就是各天的正利潤之和。

對于每次迭代，我們可以計算出價格向量中當(dāng)前元素與前一個元素之間的差值，并取該差值和0中較大的值，這樣做確保僅將正差異添加到 res 變量中，僅使用單個循環(huán)來迭代價格向量并計算最大利潤

?

• 思路二：

還是利用動態(tài)規(guī)劃的思想對其進行操作。

解題思路：

因為本題跟上一題是類似的，不同的在關(guān)于遞推公式，接下來，我就只講遞推公式的演化，其余的跟上題相同。

如果第i天持有股票即arry[i][0]， 那么遞歸公式可以像如下這樣：

這題因為是可以進行多次的買賣的，因此遞歸公式主要的變化就發(fā)生在對于 arry[i][0] 的處理，所以當(dāng)?shù)冢╥）天買入股票的時候，所持有的現(xiàn)金可能是在這之前已經(jīng)經(jīng)過買賣交易所得到的。

因此，對于第（i）天持有股票即 arry[i][0]：如果是第（i）天買入股票，所得現(xiàn)金就是昨天不持有股票的所得現(xiàn)金 減去 當(dāng)天的股票價格 即：arry[i - 1][1] - prices[i]。

???arry[i][0] =? max(arry[i - 1][0], arry[i - 1][1] - prices[i])

如果第i天持有股票即arry[i][1]， 遞歸公式跟上題相同

???arry[i][1] = max(arry[i - 1][1], prices[i] + arry[i - 1][0])

代碼展示：

• 貪心算法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
         int res=0;
         for(int i=1; i<prices.size(); ++i)
         {
             res+=max(prices[i]-prices[i-1],0);
         }
         return res;
    }
};

?性能分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

• 動態(tài)規(guī)劃：

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
        int size = prices.size();
        vector<vector<int>> arry(size, vector<int>(2, 0));
        arry[0][0] -= prices[0];
        arry[0][1] = 0;
        for (int i = 1; i < size; i++) {
            arry[i][0] = max(arry[i - 1][0], arry[i - 1][1] - prices[i]); 
            arry[i][1] = max(arry[i - 1][1], arry[i - 1][0] + prices[i]);
        }
        return arry[size - 1][1];
    }
};

?性能分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

（三）買賣股票的最佳時機 III

LeetCode題目鏈接：買賣股票的最佳時機 III

題目如下：

?

題目分析：

這道題跟上述兩道題的不同之處在于對買賣的次數(shù)限制為 至多買賣兩次，這意味著可以買賣一次，可以買賣兩次，也可以不買賣。

解題思路：

• step1：確定【arry】數(shù)組以及下標(biāo)的含義

在這道題目，我們就需要設(shè)置 5個狀態(tài)位來表示了，因為題目已經(jīng)明確給出了之多買賣兩次，因此在加上操作的情況，總共就有5種。

• 0、表示沒有任何操作?
• 1、第一次買入股票
• 2、第一次賣出股票
• 3、第二次買入股票
• 4、第二次賣出股票

?? arry[i][j] 中 i 表示第i天，j為 [0 - 4] 五個狀態(tài)，arry[i][j] 表示第i天狀態(tài)j所剩最大現(xiàn)金。

arry[0][0]：

開始時沒有任何操作，因此應(yīng)該為0，即：arry[0][0] = 0;

arry[0][1]：

在第0天準(zhǔn)備進行第一次購買操作，所以此時應(yīng)為：arry[0][1] = -prices[0];

arry[0][2]：

?大家可以理解當(dāng)天買入，當(dāng)天賣出，所以?arry[0][2] = 0;

arry[0][3]：

第0天第二次買入操作，初始值應(yīng)該是多少呢？應(yīng)該不少同學(xué)疑惑，第一次還沒買入呢，怎么初始化第二次買入呢？

第二次買入依賴于第一次賣出的狀態(tài)，其實相當(dāng)于第0天第一次買入了，第一次賣出了，然后再買入一次（第二次買入），那么現(xiàn)在手頭上沒有現(xiàn)金，只要買入，現(xiàn)金就做相應(yīng)的減少。

所以第二次買入操作，初始化為：arry[0][3] = -prices[0];

arry[0][4]：

第二次賣出股票，應(yīng)為arry[0][4] = 0;

• step2：確定遞推公式

如果第i天第一次買進股票即arry[i][1]， 那么遞歸公式可以像如下這樣：

• 如果第i天第一次買入股票了，那么?arry[i][1] = arry[i-1][0] - prices[i]
• 如果第i天沒有進行任何操作，則保持前一天買入的狀態(tài)，即：arry[i][1] = arry[i - 1][1]

???arry[i][1] = max(arry[i-1][0] - prices[i], arry[i - 1][1])

如果第i天第一次賣出股票即arry[i][2]， 那么遞歸公式可以像如下這樣：

• 如果第i天第一次賣出股票了，那么?arry[i][2] = arry[i - 1][1] + prices[i]
• 如果第i天沒有操作，則保持前一天賣出股票的狀態(tài)，即：arry[i][2] = arry[i - 1][2]

???arry[i][2] = max(arry[i - 1][1] + prices[i], arry[i - 1][2])

如果第i天第二次買進股票即arry[i][3]， 那么遞歸公式可以像如下這樣：

• 如果第i天第二次買入股票了，那么?arry[i][3] = arry[i-1][2] - prices[i]
• 如果第i天沒有進行任何操作，則保持前一天買入的狀態(tài)，即：arry[i][3] = arry[i - 1][3]

???arry[i][3] = max(arry[i - 1][2] -?prices[i], arry[i - 1][3])
? ? ? ? ? ?

如果第i天第二次賣出股票即arry[i][4]， 那么遞歸公式可以像如下這樣：

• 如果第i天第二次賣出股票了，那么?arry[i][4] = arry[i - 1][3] + prices[i]
• 如果第i天沒有操作，則保持前一次賣出股票的狀態(tài)，即：arry[i][4] = arry[i - 1][4]

??arry[i][4] = max(arry[i - 1][3] + prices[i], arry[i - 1][4])

• step3：遍歷順序

從遞歸公式可以看出，一定是從前向后遍歷，因為arry[i]，依靠arry[i - 1]的數(shù)值。

• step4：圖解展示

?

代碼展示：

以下給出的是優(yōu)化后的版本（大家可以根據(jù)理解寫出原始版本）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;

        vector<int> arry(5,0);
        arry[1] = -prices[0];
        arry[3] = -prices[0];

        for(int i=1; i<prices.size(); ++i){
            arry[1] = max(arry[1], arry[0] - prices[i]);
            arry[2] = max(arry[2], arry[1] + prices[i]);
            arry[3] = max(arry[3], arry[2] - prices[i]);
            arry[4] = max(arry[4], arry[3] + prices[i]);     
            
        }
        return arry[4];
      
    }
};

性能分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

（四）買賣股票的最佳時機 IV

LeetCode題目鏈接：買賣股票的最佳時機 IV

題目如下：

題目分析：

這道題總體說來就是上一題的進階版本，對于買賣的次數(shù)又進行了限制，這里要求至多有k次交易。

解題思路：

整體思路還是跟上題一樣，只是本題對于次數(shù)是k次

• step1：確定【arry】數(shù)組以及下標(biāo)的含義

此時狀態(tài)就不僅僅有4種了（除去沒有任何操作），而是2*k種，如果加上不做任何操作的狀態(tài)，那此處的狀態(tài)就有 2*k+1 次。

• step2：確定遞推公式

同上（大家自己推倒看看能否推倒出來）

• step3：遍歷順序

同上

• step4：圖解展示

大家可以對比上一題的圖自己畫圖試試

代碼展示：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> arry(prices.size(), vector<int>(2 * k + 1, 0));
        for (int j = 1; j < 2 * k; j += 2) {
            arry[0][j] = -prices[0];
        }
        for (int i = 1;i < prices.size(); i++) {
            for (int j = 0; j < 2 * k - 1; j += 2) {
                arry[i][j + 1] = max(arry[i - 1][j + 1], arry[i - 1][j] - prices[i]);
                arry[i][j + 2] = max(arry[i - 1][j + 2], arry[i - 1][j + 1] + prices[i]);
            }
        }
        return arry[prices.size() - 1][2 * k];
    }
};

?

到此，關(guān)于購買股票的幾個題便講解完畢了。希望對大家有所幫助，感謝各位的觀看?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-450130.html

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