買賣股票有一系列題目

以下是我找出它們之間的區(qū)別：

第一題，只能買一次，從最低價入手，最高價賣出

第二題，可以買無數(shù)次，但買了之后，必須賣出之后，再來重新買入，再賣出。

第三題，只能買兩次，但買了之后，必須賣出之后，再來重新買入，再賣出。

第四題，，只能買k次，k為既定數(shù)值，但買了之后，必須賣出之后，再來重新買入，再賣出。

第五題，可以買無數(shù)次，但在完成一次交易之后，存在一天的冷凍期，交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]。

第六題，可以買無數(shù)次，但一次交易存在手續(xù)費，在交易完成一次之后需要付出一定的手續(xù)費。

其中第一題可以說是后面題目的基礎，

第一題

給定一個數(shù)組 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)規(guī)劃的思想，

于是來說說動態(tài)規(guī)劃的做法，

第一步——遞推的思路

很顯然我們可以通過比較大小，來遍歷數(shù)組中的數(shù)，然后留下最小的，然后再來遍歷最小后面最大的數(shù)，找出最大的差值，這就是我們要輸出的dp；

第二步——確定遞推公式

定義一個兩列n行的數(shù)組存放，

然后dp[i][0]

• 第i-1天就持有股票，那么就保持現(xiàn)狀，所得現(xiàn)金就是昨天持有股票的所得現(xiàn)金 即：dp[i - 1][0]
• 第i天買入股票，所得現(xiàn)金就是買入今天的股票后所得現(xiàn)金即：-prices[i]

那么dp[i][0]應該選所得現(xiàn)金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

dp[i][1]

如果第i天不持有股票即dp[i][1]， 也可以由兩個狀態(tài)推出來

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

同樣dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

所以能得到：

 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], prices[i] + dp[i - 1][0]);
        }

然后進行初始化，

dp[0][0]=-price[0];

dp[0][1]=0;

第三步——確定遍歷順序

此題只需要一層循環(huán)，所以就用那個就行。

代碼展示：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0) return 0;
        vector<vector<int>>dp(len,vector<int>(2,0));//定義數(shù)組
        dp[0][0]-=prices[0];//初始化
        dp[0][1]=0;
        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];

    }
};

第四步——舉例

以示例1，輸入：[7,1,5,3,6,4]為例，dp數(shù)組狀態(tài)如下：

另外買賣股票的最佳時機II和買賣股票的最佳時機含手續(xù)費這兩個題目和此題是非常相似的

給出代碼先

買賣股票的最佳時機II：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0) return 0;
        vector<vector<int>>dp(len,vector<int>(2,0));//定義數(shù)組
        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];

    }
};

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

我來解釋一下這個，就是在進行一次交易賺到利益之后，把利益的值減去又再次投入的值，進行了一個投入累加。

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0) return 0;
        vector<vector<int>>dp(len,vector<int>(2,0));//定義數(shù)組
        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]-fee);//和Ⅱ相比只有此處不同
        }
        return dp[len-1][1];

    }
};

?dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);

即每次交易完成后減去交易費fee，所以只用在Ⅱ的基礎上進行一個相減即可。

三四五題是一個類型的，我放到下次來講。文章來源地址http://www.zghlxwxcb.cn/news/detail-798302.html

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