買賣股票的最佳時機

力扣題目鏈接(opens new window)

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

示例 2：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。

思路

買賣股票除了確定買賣日期之外，還需要確定當天股票的狀態(tài)

股票狀態(tài)有兩種：持有和不持有

為什么不用"買入"和"賣出"來作為狀態(tài)？

因為買入和賣出僅能代表兩種狀態(tài)，即買入和賣出

什么意思呢？就比如第i天你賣出了股票，好那第i+1天如果你不買股票，那應該是什么狀態(tài)？

如果還用“賣出”狀態(tài)來表示，那么就意味著第i+1天仍然要賣出股票，但實際上我們想表示的是這樣一種狀態(tài)：“第i天賣出股票后，如果第i+1天不買，那么第i天賣掉股票后的狀態(tài)應該持續(xù)到第i+1天”

因此，使用"買入"和"賣出"來作為狀態(tài)會漏掉一些狀態(tài)，還得單獨為那些情況設定對應的狀態(tài)進行表示

五步走

1、確定dp數組含義

根據思路，我們需要的dp數組應該是二維的

dp[i][0]:代表第i天持有股票所得到的最大收益

dp[i][1]:代表第i天不持有股票所得到的最大收益

這里在解釋一下"持有"和"不持有"

持有指的是我現在手頭上有某只股票，但不一定是今天買的，有可能是之前某一天買的，然后該狀態(tài)延續(xù)到了現在

不持有指的是手頭上已經沒有股票了，但不一定是今天賣的，有可能是之前賣掉了，然后該狀態(tài)持續(xù)到了現在（因為本題的股票只能買賣一次，因此該狀態(tài)會持續(xù)到最后一天）

2、確定遞推公式

因為dp的定義是"持有"和"不持有"兩種，因此這兩種情況需要分開討論

（1）持有股票

第i天持有股票（dp[i][0]）的狀態(tài)可以通過兩種情況推導得到：

• 第i天買了股票
• 第i - 1天之前買了股票

因為本題只能買賣一次股票，因此不管在哪天買入股票，都是第一次買入

因為我們的初始現金是0，所以在買入股票之后，此時的最大收益是 -price[i]，即dp[i][0] = -price[i]。因為買股票花錢了嘛，此時的狀態(tài)變?yōu)?strong>持有股票

然后如果是第i天不買入股票，但狀態(tài)仍是持有股票的話，那么此時的狀態(tài)是dp[i][0] = dp[i - 1][0]

綜上，取兩者最大的情況，那么持有股票時的遞推公式為：dp[i][0] = max(dp[i - 1][0], -price[i])

（2）不持有股票

第i天持有股票（dp[i][1]）的狀態(tài)可以通過兩種情況推導得到：

• 第i天賣了股票
• 第i - 1天之前賣了股票

如果是在第i天賣了股票，那么此時除了狀態(tài)需要轉換為持有股票（并且是i - 1天持有，因為第i天賣掉了就不持有了），還需要加上第i天的股價price[i]作為收益，即dp[i][1] = price[i] + dp[i - 1][0]

也就是說，如果當前的狀態(tài)是不持有并且原因是，那在第i天還沒賣股票時，此時的狀態(tài)應該是dp[i][0]，賣掉之后狀態(tài)轉變?yōu)?code>dp[i][1]

顯然不能用dp[i][1] = dp[i][0]來表示這件事情

那么可以用price[i]表示第i天賣了股票（因為得到了收益），然后再用dp[i - 1][0]表示我前一天確實有這個股票

兩件事情加起來就可以證明我在第i天賣了股票

如果是在第i - 1天之前賣了股票，那么此時狀態(tài)還是不持有股票，即dp[i][1] = dp[i - 1][1]

綜上，取兩者最大的情況，那么不持有股票時的遞推公式為：dp[i][1] = max(dp[i - 1][1], price[i] + dp[i - 1][0])

3、初始化dp數組

從兩種情況下的遞推公式來看，dp[0][1]和dp[0][0]是遞推的基礎，因此需要對其進行初始化

結合dp數組的定義，dp[0][1]是第0天不持有股票所得到的最大收益，那沒有股票肯定是0啊，而且我們初始資金也是0，即dp[0][1]=0

而dp[0][0]則是第0天持有股票所得到的最大收益，因為是第0天，所以不會存在前一天的情況

因此持有的股票一定是第0天購買的，所以dp[0][0] = -price[i]

4、確定遍歷順序

dp[i][1]由dp[0][1]推導而來，因此需要順序遍歷

代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len == 0) return 0;
        //定義dp數組
        vector<vector<int>> dp(len, vector<int>(2));
        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        //遍歷dp數組
        for(int i = 1; i < len ;++i){
            dp[i][0] = max(dp[i - 1][0], -prices[i]);//持有股票
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不持有股票
        }
        
        return dp[len - 1][1];
    }
};

為什么返回值是dp[len - 1][1]而不是max(dp[len][0], dp[len][1])？

如果認為max(dp[len][0], dp[len][1])是返回值的話，存在兩個錯誤

（1）len - 1才是最后一天，不是len

（2）題目要求最大利潤，但沒有要求具體在哪個狀態(tài)達成

在這個題目中，只需要求最終的最大利潤，而不需要知道具體是在哪個狀態(tài)（持有股票或不持有股票）達到了最大利潤，因此直接返回dp[len - 1][1]即可。這是因為題目中規(guī)定，最后一天必須賣出所有持有的股票，而不是可以選擇繼續(xù)持有。

在遍歷到最后一天后，dp[len-1][0]表示最后一天持有股票的最大收益，而dp[len-1][1]則表示最后一天不持有股票的最大收益。

我們只需要考慮最后一天的狀態(tài)，也就是持有股票和不持有股票的兩種情況，因為最后一天無法再進行任何交易了，只有賣出股票才能獲得收益。因此，我們只需要返回最后一天不持有股票的最大收益 dp[len-1][1] 即可。

買賣股票的最佳時機II

力扣題目鏈接(opens new window)

給定一個數組，它的第 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。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

思路

基本的思路和 I 一致
dp數組的含義仍然是：持有/不持有股票的最大收益

唯一不同的地方，就是推導dp[i][0]和dp[i][0]的時候，第i天買入股票的情況。

這里再推導一下所有的情況吧

（1）持有股票dp[i][0]

如果是第i天買入的，那么要用沒有持有該股票時有的錢（也就是不持有你現在要買的股票時，可以得到的最大收益）減去股票的售價，即dp[i][0] = dp[i - 1][1] - prices[i]

如果是第i-1天買入的，就還是和上一題一樣，狀態(tài)延續(xù)到第i天即可，即dp[i][0] = dp[i - 1][0]

綜上，dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有

（2）不持有股票dp[i][1]

如果是第i天賣掉的，那就要用持有該股票時有的錢加上賣股票得的錢，即dp[i][1] = dp[i - 1][0] + prices[i]

如果是第i-1天賣掉的，延續(xù)第i天的狀態(tài)即可，即dp[i][1] = dp[i - 1][1]

綜上，dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不持有

代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len  = prices.size();//獲取prices數組長度（天數）
        if(len == 0 ) return 0;
        vector<vector<int>> dp(len, vector<int>(2));//創(chuàng)建dp數組
        dp[0][0] = -prices[0];//初始化
        dp[0][1] = 0;

        for(int i = 1; i < len; ++i){
            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]);//不持有
        }
        return dp[len - 1][1];//最后一天要求把股票賣掉，返回不持有股票的最大金錢數
    }
};

買賣股票的最佳時機III

力扣題目鏈接(opens new window)

給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1: 輸入：prices = [3,3,5,0,0,3,1,4] 輸出：6 解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。隨后，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3。

示例 2： 輸入：prices = [1,2,3,4,5] 輸出：4 解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4。注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3： 輸入：prices = [7,6,4,3,1] 輸出：0 解釋：在這個情況下, 沒有交易完成, 所以最大利潤為0。

示例 4： 輸入：prices = [1] 輸出：0

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^5

思路

與之前的兩題最大的不同是，之前一天只可以進行一次交易（買賣），總的交易次數也只有1次

而現在一天可以交易兩次，總的次數也是兩次

至多買賣兩次，意味著可以買賣一次，可以買賣兩次，也可以不買賣。

五步走

1、確定dp數組含義

回憶一下，之前只能買賣一次時，我們有兩種情況，即：第i天持有或不持有股票

現在因為可以進行兩次買賣，所以第i天可能有的所有情況（假設在第i天就進行兩次交易，就會有四種情況）有四種：

• 0、沒有操作--dp[i][0]
• 1、第i天第一次持有股票--dp[i][1]
• 2、第i天第一次不持有股票--dp[i][2]
• 3、第i天第二次持有股票--dp[i][3]
• 4、第i天第二次不持有股票--dp[i][4]

即dp[i][j]中，i表示第i天，j表示狀態(tài)

dp[i][j]表示第i天狀態(tài)j所剩最大現金

2、確定遞推公式

dp[i][0]先不用管，后面要初始化

達到dp[i][1]狀態(tài)（第一次持有股票），有兩個具體操作：

• 操作一：第i天買入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]（用前一天狀態(tài)下還剩的錢減去第i天買入股票的價格）
• 操作二：第i天沒有操作，而是沿用前一天買入的狀態(tài)，即：dp[i][1] = dp[i - 1][1]

取最大結果：dp[i][1] = max(dp[i- 1][0] - prices[i], dp[i - 1][1]);

dp[i][2]（第一次不持有股票）同理：

• 操作一：第i天賣出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]（ ）
• 操作二：第i天沒有操作，沿用前一天賣出股票的狀態(tài)，即：dp[i][2] = dp[i - 1][2]

取最大結果：dp[i][2] = max(dp[i - 2][1] - prices[i], dp[i - 1][2]);

按上面的形式可以把剩余的情況在不同操作下的狀態(tài)推導出來：

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

3、初始化dp數組

（1）如果第0天沒有操作，那就是0，即dp[0][0] = 0

（2）如果第0天第一次操作

• 在第0天第一次買入，初始現金為0，那么現在要扣除買股票的錢，即dp[0][1] = -prices[0]
• 在第0天第一次賣出，即dp[0][2] = 0

如果第0天的第一次操作就是賣出，那此時都沒有東西，賣什么呢？

這種情況可以理解為在同一天先買入了，然后又在當天賣出

買賣都是相同的價格，相當于錢花出去了又原路返回，因此dp[0][2] = 0

由此我們可以發(fā)現，第一次賣出的操作是依賴第一次買入操作的

（3）如果第0天第二次操作

• 在第0天第二次買入。dp[0][3] = -prices[0]

所謂的“第二次買入”，意味著我之前已經買入過一次了，也就是說第二次買入依賴于第一次賣出的狀態(tài)

又因為題目規(guī)定買完必須先賣掉才能再買，所以“第二次買入”時，已經經過了第一次買入和賣出

因此在第0天第二次買入時，手頭上的錢仍然是0，那么買入之后的狀態(tài)自然就是 -prices[0]

• 在第0天第二次賣出。dp[0][4] = 0

與在第0天第一次賣出同理

4、確定遍歷順序

i由i-1推出，因此仍是從小到大遍歷，即順序遍歷文章來源地址http://www.zghlxwxcb.cn/news/detail-424156.html

代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        //創(chuàng)建dp數組
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        //初始化,根據分析進行初始化
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];

        //遍歷dp數組
        for(int i = 1; i < prices.size(); ++i){
            dp[i][0] = dp[i - 1][0];//不進行操作
            //第i天第一次進行操作
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不操作|買入股票，用前一天狀態(tài)下還剩的錢減去第i天買入股票的價格
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);//不操作|賣出股票，用前一天狀態(tài)下還剩的錢加上第i天賣掉股票的收益

            //第i天第二次進行操作
            dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] - prices[i]);//不操作|買入股票
            dp[i][4] = max(dp[i - 1][4],dp[i - 1][3] + prices[i]);//不操作|賣出股票
        }
        return dp[prices.size() - 1][4];
    }
};

買賣股票的最佳時機IV

力扣題目鏈接(opens new window)

給定一個整數數組 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1： 輸入：k = 2, prices = [2,4,1] 輸出：2 解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2。

示例 2： 輸入：k = 2, prices = [3,2,6,5,0,3] 輸出：7 解釋：在第 2 天 (股票價格 = 2) 的時候買入，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4。隨后，在第 5 天 (股票價格 = 0) 的時候買入，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3 。

提示：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

思路

本題與上題的不同點在于買賣次數，現在我們可以任意買賣k次了

從上題來看，買賣兩次已經需要列出4個狀態(tài)了（不算不操作狀態(tài)），因此在k次交易的條件下，羅列處所有狀態(tài)是可能的

需要使用循環(huán)去控制

五步走

1、dp數組的含義

與上一題一樣

二維數組 dp[i][j] ：dp[i][j]表示第i天狀態(tài)j所剩最大現金

j的狀態(tài)可以表示為：

• 0 表示不操作
• 1 第一次買入
• 2 第一次賣出
• 3 第二次買入
• 4 第二次賣出
• .....

除了0以外，上述狀態(tài)的規(guī)律可以總結為：偶數賣出，奇數買入

因為買賣次數變成k次，每多一次買賣會新增兩種狀態(tài)，所以dp數組的大小要設置為2k + 1

vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));

2、確定遞推公式

正如上面的分析，k次買賣的話是不可能都列出來所有狀態(tài)的，因此需要進行抽象，抽象出一個通用的遞推公式

先來看看上一題中，兩次買賣時的遞推公式：

			dp[i][0] = dp[i - 1][0];//不進行操作
            //第i天第一次進行操作
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);//不操作|買入股票，用前一天狀態(tài)下還剩的錢減去第i天買入股票的價格
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);//不操作|賣出股票，用前一天狀態(tài)下還剩的錢加上第i天賣掉股票的收益

            //第i天第二次進行操作
            dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] - prices[i]);//不操作|買入股票
            dp[i][4] = max(dp[i - 1][4],dp[i - 1][3] + prices[i]);//不操作|賣出股票

這里可以發(fā)現，二維dp數組中，第二個維度我們是寫成具體數字的，用來表示買入和賣出狀態(tài)

可以使用一個變量j來代替具體的數字，j + 1表示買入；j + 2表示賣出

使用for循環(huán)控制j，j從0開始循環(huán)，每次自增2

for(int j = 0; i < 2 * k; j += 2){
    dp[i][j] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);//不操作|奇數買入,用前一天狀態(tài)下還剩的錢減去第i天買入股票的價格
    dp[i][j] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);//不操作|偶數賣出,用前一天狀態(tài)下還剩的錢加上第i天賣掉股票的收益
}

類比j為奇數是買，偶數是賣的狀態(tài)。

為什么j是小于2 * k，而不是別的值，比如2 * k - 1 ？

遇到邊界不確定的情況時，就代入具體值來判斷是否合理

這里假設一共至多可以買賣2次

如果j < 2 * k ,那么 j < 4

以上面 兩次買賣時的遞推公式 為例來看

當循環(huán)開始，

j = 0，所以 j + 1 指向dp[i][1]， j + 2 指向dp[i][2]，一切正常

j = 2，所以 j + 1 指向dp[i][3]， j + 2 指向dp[i][4]，一切正常

j = 3，所以 j + 1 指向dp[i][3]， j + 2 指向dp[i][4]，一切正常

j = 4，循環(huán)結束，所有狀態(tài)被完整覆蓋，邊界正確

3、初始化dp數組

基本上與買賣III的思路一致

（1）如果第0天沒有操作，那就是0，即dp[0][0] = 0

（2）如果第0天第一次操作

• 在第0天第一次買入，初始現金為0，那么現在要扣除買股票的錢，即dp[0][1] = -prices[0]
• 在第0天第一次賣出，即dp[0][2] = 0

（3）如果第0天第二次操作

• 在第0天第二次買入。dp[0][3] = -prices[0]
• 在第0天第二次賣出。dp[0][4] = 0

（關于推導的細節(jié)與注釋詳見買賣III）

我們還是從上面初始化中總結規(guī)律進行抽象

即：j為奇數時候，要初始化為-prices[0]；j為偶數時候，要初始化為0；

使用for循環(huán)進行初始化

for(int j = 1; j < 2 * k; j += 2){
    dp[0][j] = -prices[0];//0在創(chuàng)建dp數組的時候就初始化了
}

為什么j是小于2 * k，而不是別的值，比如2 * k - 1 ？

還是代入來看, 這里假設至多可以買賣2次，那么 j < 4

當j = 1時，奇數初始化為-prices[0]

然后自增2，j = 3，奇數初始化為-prices[0]

再自增就超過4，結束循環(huán)，過程沒有問題

4、確定遍歷順序

i由i-1推出，因此仍是從小到大遍歷，即順序遍歷

代碼

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

        //創(chuàng)建dp數組
        vector<vector<int>> dp(prices.size() + 1, vector<int>(2 * k + 1, 0));

        //初始化dp數組
        for(int j = 1; j < 2 * k; j += 2){
            dp[0][j] = -prices[0];//0在創(chuàng)建dp數組的時候就初始化了，所以不用在此處初始化
        }

        //遍歷dp數組
        for(int i = 1; i < prices.size(); ++i){
            for(int j = 0; j < 2 * k; j += 2){
                //不操作|奇數買入,用前一天狀態(tài)下還剩的錢減去第i天買入股票的價格
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
                //不操作|偶數賣出,用前一天狀態(tài)下還剩的錢加上第i天賣掉股票的收益
                dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
            }
        }
        return dp[prices.size() - 1][2 * k];//返回最后一天賣掉股票后的總金額
    }
};

到了這里，關于【LeetCode動態(tài)規(guī)劃#12】詳解買賣股票I~IV，經典dp題型的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！