買賣股票相關的動態(tài)規(guī)劃題目

1.最佳買賣股票時機含冷凍期

力扣鏈接：力扣

給定一個整數(shù)數(shù)組prices，其中第??prices[i]?表示第?i?天的股票價格 。?

設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

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

?首先我們分析一下題目，題目中的要點是賣出股票后第二天不能買入，并且每次買新的股票前都要出售掉原先的股票，有了這個限制條件，我們就很容易分析出這道題是多狀態(tài)的dp。

1.狀態(tài)表示

當我們以dp[i]表示第i天結束的最大利潤時，我們發(fā)現(xiàn)無法寫出狀態(tài)轉移方程，因為要求第i天的最大利潤，我們要看第i天是否是冷凍期或者是否手中無股票或者手中有股票，所以我們將有三種狀態(tài)表示：

f[i]表示第i天手中有股票的最大利潤

g[i]表示第i天手中沒有股票的最大利潤

s[i]表示第i天處于冷凍期的最大利潤

2.狀態(tài)轉移方程

首先我們要分析每種狀態(tài)，比如我們第i天持有股票，那么從哪一個狀態(tài)可以到有股票的狀態(tài)呢？當前一天也就是i-1天就有股票的時候，我們什么也不干到了第i天還是處于有股票的狀態(tài)。當前一天是沒有股票的狀態(tài)，那么我們在前一天買股票到了第i天就處于有股票狀態(tài)。

所以f[i] = max(f[i-1],g[i-1] - p[i])

接下來我們分析沒有股票的狀態(tài)，首先如果前一天就沒有股票，那么什么也不干到了第i天還是處于沒有股票的狀態(tài)。如果前一天是冷凍期，那么什么也不干到了第i天就自動處于沒有股票狀態(tài)（因為冷凍期一定是賣出股票了，一旦賣出手中就沒有股票了）。

所以 g[i] = max(g[i-1],s[i-1])

接下來我們分析冷凍期，冷凍期一定是賣出股票才會有的，所以前一天是有股票狀態(tài)，然后將股票賣出，第i天就是冷凍期。

所以s[i] = f[i-1] + p[i];

3.初始化

從狀態(tài)轉移方程我們可以看到每次需要前一天的利潤，那么只有第1天會越界，所以我們直接初始化三個表的第一天，第一天要有股票那么就得買入，買入利潤就從0變成負數(shù)，所以f[0] = -p[0]

第一天沒有股票那么什么也不干就可以，所以g[0] = 0

第一天就處于冷凍期那么利潤一定為0?所以s[0] = 0

4.填表

從左向右，三個表一起填

5.返回值

返回三個表的最后一天的最大值。

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

當然我們也可以將代碼優(yōu)化一下，最后一天如果手里還有股票沒賣出去，那么這一天的利潤一定是比無股票狀態(tài)和冷凍期狀態(tài)低的，所以我們只需要返回賣出股票狀態(tài)的最大值即可：

當然，我們上面用三個一維數(shù)組表示狀態(tài)是比較冗余的，我們可以用二維數(shù)組來表示，代碼如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(3,0));
        dp[0][0] = -prices[0];
        for (int i = 1;i<n;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][2]);
            dp[i][2] = dp[i][0] + prices[i];
        }
        return max(dp[n-1][1],dp[n-1][2]);
    }
};

?上面我們是以dp[i][0]表示有股票狀態(tài)，dp[i][1]表示無股票狀態(tài)，dp[i][2]表示冷凍期。

2.買賣股票的最佳時機含手續(xù)費

力扣鏈接：力扣

給定一個整數(shù)數(shù)組?prices，其中?prices[i]表示第?i?天的股票價格 ；整數(shù)?fee?代表了交易股票的手續(xù)費用。

你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。

返回獲得利潤的最大值。

注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費。

?這道題是我們做的第一道題的變種，我們先來分析一下這道題中的細節(jié)：

首先這次沒有冷凍期了可以隨便交易，但是每筆交易需要付手續(xù)費，這里要注意了，一筆交易是指有股票然后賣出，可以理解為只有賣出的時候需要交手續(xù)費。并且這道題和第一題一樣，都是只有賣出原先的股票才能購買新的股票。

1.狀態(tài)表示

我們根據(jù)上一題的經(jīng)驗，直接用f[i]表示第i天手中有股票的最大利潤，用g[i]表示第i天手中沒有股票的最大利潤。

2.狀態(tài)轉移方程

?因為此題只有兩種狀態(tài)，所以我們直接分析：

當前一天也就是i-1天就有股票的時候，我們什么也不干到了第i天還是處于有股票的狀態(tài)。當前一天是沒有股票的狀態(tài)，那么我們在前一天買股票到了第i天就處于有股票狀態(tài)。

所以f[i] = max(f[i-1],g[i-1]-p[i])

首先如果前一天就沒有股票，那么什么也不干到了第i天還是處于沒有股票的狀態(tài)。如果前一天有股票，那么我們賣出股票就變成了沒有股票狀態(tài)。

所以g[i] = max(g[i-1],f[i-1] + p[i] -fee)? ?//注意賣出股票需要支付手續(xù)費

3.初始化

只有第一天會越界，所以我們直接初始化兩個表的第一天的最大利潤：

第一天要有股票那么就得買入，買入利潤就從0變成負數(shù)，所以f[0] = -p[0]

第一天沒有股票那么什么也不干就可以，所以g[0] = 0

4.填表

從左向右，兩個表一起填

5.返回值

返回最后一天是賣出狀態(tài)的最大利潤即可。（因為最后一天手中沒股票一定比手中有股票的利潤大）

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

3.買賣股票的最佳時機 III

力扣鏈接：力扣

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

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

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

?這道題和我們上一題基本一樣，就是多了一個最多完成兩筆交易的限制，下面我們直接開始分析。

1.狀態(tài)表示

我們根據(jù)前兩道題的經(jīng)驗，先以f[i]表示第i天手中有股票的最大利潤，g[i]表示第i天手中沒有股票的最大利潤，但是我們發(fā)現(xiàn)這樣的狀態(tài)表示無法限制最多完成兩筆交易，所以我們直接多加一個狀態(tài)就可以了，用f[i][0]代表第i天進行了0筆交易手中有股票的最大利潤，f[i][1]代表第i天進行了1筆交易手中有股票的最大利潤，f[i][2]代表第i天進行了2筆交易手中有股票的最大利潤，g表同理。

所以f[i][j]代表第i天交易了j次，處于有股票狀態(tài)。

g[i][j]代表第i天交易了j次，處于沒有股票的狀態(tài)。

2.狀態(tài)轉移方程

當前一天也就是i-1天就有股票的時候，我們什么也不干到了第i天還是處于有股票的狀態(tài)。當前一天是沒有股票的狀態(tài)，那么我們在前一天買股票到了第i天就處于有股票狀態(tài)。

所以f[i][j]?= max(f[i-1][j],g[i-1][j]-p[i])? 注意：前一天處于有股票的狀態(tài)，那么什么也不干第i天還是處于有股票的狀態(tài)，所以我們的交易次數(shù)是不變的，還是j次。如果前一天是沒有股票狀態(tài)，那么買了股票就到了有股票狀態(tài)，但是我們要注意只有賣出股票才算一次交易，所以這里還是j次交易沒有改變。

首先如果前一天就沒有股票，那么什么也不干到了第i天還是處于沒有股票的狀態(tài)，并且交易次數(shù)不發(fā)生改變。如果前一天有股票，那么我們賣出股票就變成了沒有股票狀態(tài)，但是賣出股票就會增加一次交易，而我們要求的實際上是第i天的交易，也就是說增加完一次交易后交易次數(shù)才變成了j，那么在求前一天的有股票的利潤時應該按照j-1的交易次數(shù)（因為前一天有股票，第i天賣出變成沒有股票狀態(tài)，一旦賣出交易次數(shù)+1，默認第i天是j次交易的話，那么第i-1天就是j-1次交易）

所以g[i] = max(g[i-1][j],f[i-1][j-1]+p[i])

3.初始化

通過狀態(tài)轉移方程可以發(fā)現(xiàn)，每次要求前一天相應交易次數(shù)的最大值，而為了原來表中的數(shù)據(jù)不影響取最大值，就將表中每個數(shù)據(jù)初始化為整形的最小值，但是由于有-p[i]的存在，會使整形的最小值溢出，所以我們只取一半整形的最小值就好了。

第一天要有股票并且不交易（也就是不賣出）那么利潤就從0變成負數(shù)，所以f[0][0]?= -p[0]

第一天沒有股票并且交易次數(shù)為0，那么什么也不干就可以，所以g[0][0] = 0

4.填表

每一行從上往下，每一列從左向右，兩個表一起填

5.返回值

返回最后一天是賣出狀態(tài)的并且交易是0,1,2三種中的最大利潤即可。（因為題目只限制不超過2筆交易，但是不能保證交易次數(shù)多一定利潤大，當只有一天的股票的時候，不交易是利潤最大的）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        const int Min = -0x3f3f3f3f;
        vector<vector<int>> f(n,vector<int>(3,Min));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1;i<n;i++)
        {
            for (int j = 0;j<3;j++)
            {
                f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if (j>=1)
                {
                    g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
            }
        }
        int ret = g[n-1][0];
        for (int i = 1;i<3;i++)
        {
            if (ret<g[n-1][i])
            {
                ret = g[n-1][i];
            }
        }
        return ret;
    }
};

需要注意的是，我們的f[i-1][j-1]這種情況只有在j>=1的時候才不會越界，所以當j = 0的時候我們只需要讓g[i][j] = g[i-1][j]

4.買賣股票的最佳時機 IV

力扣鏈接：力扣

給定一個整數(shù)數(shù)組?prices?，它的第?i?個元素?prices[i]?是一支給定的股票在第?i?天的價格，和一個整型?k?。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成?k?筆交易。也就是說，你最多可以買?k?次，賣?k?次。

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

?其實大家不難發(fā)現(xiàn)，這道題和我們上一題的區(qū)別只有交易的最大限制，而我們也只需要將上一題的兩筆交易修改為k筆交易即可。

1.狀態(tài)表示

f[i][j]代表第i天交易了j次，處于有股票狀態(tài)。

g[i][j]代表第i天交易了j次，處于沒有股票的狀態(tài)。

2.狀態(tài)轉移方程

當前一天也就是i-1天就有股票的時候，我們什么也不干到了第i天還是處于有股票的狀態(tài)。當前一天是沒有股票的狀態(tài)，那么我們在前一天買股票到了第i天就處于有股票狀態(tài)。

所以f[i][j]?= max(f[i-1][j],g[i-1][j]-p[i])? 注意：前一天處于有股票的狀態(tài)，那么什么也不干第i天還是處于有股票的狀態(tài)，所以我們的交易次數(shù)是不變的，還是j次。如果前一天是沒有股票狀態(tài)，那么買了股票就到了有股票狀態(tài)，但是我們要注意只有賣出股票才算一次交易，所以這里還是j次交易沒有改變。

首先如果前一天就沒有股票，那么什么也不干到了第i天還是處于沒有股票的狀態(tài)，并且交易次數(shù)不發(fā)生改變。如果前一天有股票，那么我們賣出股票就變成了沒有股票狀態(tài)，但是賣出股票就會增加一次交易，而我們要求的實際上是第i天的交易，也就是說增加完一次交易后交易次數(shù)才變成了j，那么在求前一天的有股票的利潤時應該按照j-1的交易次數(shù)（因為前一天有股票，第i天賣出變成沒有股票狀態(tài)，一旦賣出交易次數(shù)+1，默認第i天是j次交易的話，那么第i-1天就是j-1次交易）

所以g[i] = max(g[i-1][j],f[i-1][j-1]+p[i])

3.初始化

通過狀態(tài)轉移方程可以發(fā)現(xiàn)，每次要求前一天相應交易次數(shù)的最大值，而為了原來表中的數(shù)據(jù)不影響取最大值，就將表中每個數(shù)據(jù)初始化為整形的最小值，但是由于有-p[i]的存在，會使整形的最小值溢出，所以我們只取一半整形的最小值就好了。

第一天要有股票并且不交易（也就是不賣出）那么利潤就從0變成負數(shù)，所以f[0][0]?= -p[0]

第一天沒有股票并且交易次數(shù)為0，那么什么也不干就可以，所以g[0][0] = 0

4.填表

每一行從上往下，每一列從左向右，兩個表一起填

5.返回值

返回最后一天是賣出狀態(tài)的并且交易是K種中的最大利潤即可。（因為題目只限制不超過K筆交易，但是不能保證交易次數(shù)多一定利潤大，當只有一天的股票的時候，不交易是利潤最大的）

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        const int Min = -0x3f3f3f3f;
        vector<vector<int>> f(n,vector<int>(k+1,Min));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1;i<n;i++)
        {
            for (int j = 0;j<k+1;j++)
            {
                f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if (j>=1)
                {
                    g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
            }
        }
        int ret = g[n-1][0];
        for (int i = 1;i<k+1;i++)
        {
            if (ret<g[n-1][i])
            {
                ret = g[n-1][i];
            }
        }
        return ret;
    }
};

注意：我們上一題兩筆交易的時候，要開3個位置，這是因為還要0筆交易也就是不交易的情況，所以這道題給出K筆交易的時候我們還要多加1用來表示第0筆交易。文章來源地址http://www.zghlxwxcb.cn/news/detail-535975.html

到了這里，關于60題學會動態(tài)規(guī)劃系列：動態(tài)規(guī)劃算法第四講的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！