昨天已經(jīng)把打家劫舍的問題解決了，最后一個題目涉及到樹形dp比較難（等到二刷的時候再重點看下），今天的任務(wù)是解決股票問題。

今日任務(wù)：

• 121.買賣股票的最佳時機
• 122.買賣股票的最佳時機II

題目一：買賣股票的最佳時機

Leetcode題目：【121.買賣股票的最佳時機】

因為此題中買賣股票只能買賣一次。動態(tài)規(guī)劃是解決整套股票交易的固定方法。
按照動規(guī)五部曲：
（1）定義dp數(shù)組： i僅僅表示賣出的這種狀態(tài)，不一定是當(dāng)天去買或者賣股票
dp[i][0]表示持有這支股票，所得到的最大現(xiàn)金；
dp[i][1]表示不持有這支股票，所得到的最大現(xiàn)金。
注意：dp[i][0]不一定是當(dāng)天有這支股票，有可能是0 ~ i-1天之間買入的；dp[i][1]也是同理。
最終要求的結(jié)果 max(dp[price.size()-1][0] , dp[price.size()-1][1])
（2）定義遞推公式：
總結(jié)：持有就是可能是之前持有和現(xiàn)在持有；不持有可能是之前賣了也可能是現(xiàn)在賣了。
dp[i][0]：之前持有：dp[i-1][0]， 現(xiàn)在持有：-price[i]（買的話肯定是第一次買），所以dp[i][0] = max(dp[i-1][0], -price[i])；
dp[i][1]：之前賣了：dp[i-1][1]，現(xiàn)在賣了：dp[i-1][0] + price[i]，所以dp[i][1] = max(dp[i-1][1], dp[i-1][0] + price[i]);
（3）初始化：
dp[0][0] = -price[0]；dp[0][1] = 0;
（4）遍歷順序：
從左到右即可。
（5）打印dp數(shù)組即可：
將dp數(shù)組打印出來就可以了。

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

題目二：買賣股票的最佳時機II

Leetcode題目：【122.買賣股票的最佳時機II】

這個題與上面的不同的是，可以一支股票可以買賣多次，還是用動態(tài)規(guī)劃解決股票流轉(zhuǎn)的問題。

再解法上與上一題的區(qū)別是持有股票的遞推公式不同。為了對股票投資的最佳時機問題有更清楚的認(rèn)識，下面自己按照動規(guī)五部曲進行分析：

（1）確定dp數(shù)組的含義，定義二維的：
dp[i][0]表示持有這支股票，能收獲的最大金額數(shù)；
dp[i][1]表示不持有這支股票，能收回的最大金額數(shù)。
（2）確定遞推公式：
總結(jié)：持有這支股票：之前持有或者現(xiàn)在持有；不持有這支股票：之前賣了，或者現(xiàn)在賣了；
dp[i][0] = max(dp[i-1][0], dp[i][1] - prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
（3）確定初始化條件：
dp[0][0] = -prices[0];
dp[0][1] = 0；
（4）遍歷順序：
從左到右即可；
（5）打印dp數(shù)組。文章來源地址http://www.zghlxwxcb.cn/news/detail-840210.html

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

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