代码随想录算法训练营第五十一天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

代码随想录算法训练营第五十一天

121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

1. 确定dp数组以及下标的含义：dp[i][0]：第i天不持有股票的最大利润，dp[i][1]：第i天持有股票的最大利润
2. 确定递推公式：
   1. 第i天不持有有2种情况：前一天持有，当天卖出不持有；前一天不持有，当天也不持有。所以dp[i][0] = max(dp[i-1][1]+prices[i]，dp[i-1][0]）
   2. 第i天持有也有两种情况：前一天持有当天继续持有；前一天不持有，当天买入。所以dp[i][1] = max(dp[i-1][1],-prices[i])。（只买卖一次）
3. dp数组如何初始化：第一天不持有就是dp[0][0] = 0；第一天持有就是第一天买入dp[0][1] = -prices[0]
4. 确定遍历顺序：从前向后遍历。
5. 打印dp数组。

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

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

题目链接：122.买卖股票的最佳时机II

1. 确定dp数组以及下标的含义：dp[i][0]：第i天不持有股票的最大利润，dp[i][1]：第i天持有股票的最大利润
2. 确定递推公式：
   1. 第i天不持有有2种情况：前一天持有，当天卖出不持有；前一天不持有，当天也不持有。所以dp[i][0] = max(dp[i-1][1]+prices[i]，dp[i-1][0]）
   2. 第i天持有也有两种情况：前一天持有当天继续持有；前一天不持有，当天买入。所以dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])。
3. dp数组如何初始化：第一天不持有就是dp[0][0] = 0；第一天持有就是第一天买入dp[0][1] = -prices[0]
4. 确定遍历顺序：从前向后遍历。
5. 打印dp数组。

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