121.买卖股票的最佳时机、122.买卖股票的最佳时机Ⅱ

121.买卖股票的最佳时机

显然这道题可以用普通的方法做，可能会更容易想，也更容易做，但是由于在学习动态规划，因此此文只给动态规划的解法。
对于每一天的状况，我们给予它两种状态，持有股票以及没有持股票，用一个数组dp[ii][0]表示第ii天没有持股票，dp[ii][1]表示第ii天持有股票。而其如何进行动态处理呢？
对于第ii天，如果持有股票，那么如果想要收益最高，那么股票的价格应该更低，因此，如果今天的股票价格比之前记录的更低，那么我们让它进行更新，也就是让dp[ii][1] = max(-prices[ii],dp[ii][1]);没有持股票的话，就是今天将股票卖出去的钱，和昨天可以赚的最多金额进行比较，如果今天的钱更多，我们就进行更新。dp[ii][0] = max(dp[ii-1][1]+prices[ii],dp[ii-1][0]);
动态四部曲
1.dp二维数组的含义，dp[ii][0]表示第ii天没有持股票的最大金额，dp[ii][1]表示第ii天持有股票的最大金额。
2.dp二维数组的推导过程，
dp[ii][1] 取昨天金额和今天卖出股票的金额最大值，dp[ii][1] = max(-prices[ii],dp[ii][1]);
dp[ii][0]取昨天记录的股票价格和今天股票价格的更小值，dp[ii][0] = max(dp[ii-1][1]+prices[ii],dp[ii-1][0]);
3.dp二维数组的初始化，令dp[0][0]为0，dp[0][1] 为第一天股票的负值。
4.从前向后进行遍历。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>>dp(prices.size(),vector<int>(2,0));//0不持有股票，1持有股票
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int ii =1;ii<prices.size();ii++)
            {
                dp[ii][0] = max(dp[ii-1][1]+prices[ii],dp[ii-1][0]);
                dp[ii][1] = max(dp[ii-1][1],-prices[ii]);
            }
        return dp[prices.size()-1][0];
    }
};

122.买卖股票的最佳时机Ⅱ

与上一题相似，这道题也是买卖股票，区别在于本道题的股票可以多次买卖，因此，需要记录第ii天的最大现金。因此，dp[ii][0]dp[ii][1]数组的含义为未持有与持有股票的最大现金。
推导公式为：第ii天没有持有股票的话，为前一天没有持股票的最大现金与今天卖掉股票的最大现金取较大者。dp[ii][0] = max(dp[ii-1][0],prices[ii]+dp[ii-1][1]);
第ii天持有股票的话，就是前一天没有持股票减去今天的股票价格与前一天的股票价格取较大者。dp[ii][1] = max(dp[ii-1][1],dp[ii-1][0]-prices[ii]);

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {//0没有买股票的最大现金，1买了股票的最大现金
        vector<vector<int>>dp(prices.size(),vector<int>(2,0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int ii = 1;ii<prices.size();ii++)
        {
            dp[ii][0] = max(dp[ii-1][0],prices[ii]+dp[ii-1][1]);
            dp[ii][1] = max(dp[ii-1][1],dp[ii-1][0]-prices[ii]);
        }
        return dp[prices.size()-1][0];
    }
};