代码随想录算法训练营第四十六天|121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 123.买卖股票的最佳时机III

LeetCode 121. 买卖股票的最佳时机

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

踩坑：和打家劫舍有点像当时有差别，一开始想用打家劫舍的dp数组含义，但是第 i 天买入，不买，卖出难以用前i-1天获得的最大利润表示。

思路：

1. dp数组含义：dp[i][0/1]：第 i 天不持有该股票/持有该股票的最大利润。
2. 递推公式：dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); dp[i][1] = max(dp[i-1][1], -pricesp[i]);这里需要注意的是，由于该题是一次买入，一次卖出，所以如果第 i 天持有了股票，一定是第一次买入，利润为-prices[i]，而不用表示成dp[i-1][0]-pricesp[i]，这样会变成多次买入卖出。
3. 初始化：dp[0][0] = 0; dp[0][1] = -prices[0];
4. 遍历顺序：从小到大

代码：

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

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

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

踩坑：无

思路：就是上一题变成了可以多次买入卖出。

代码：

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

LeetCode 123.买卖股票的最佳时机III

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

踩坑：看视频

思路：题目要求是至多交易两次，难在状态的表示。同时提示prices的大小可以为1，说明支持当天同时买入卖出。

1. dp数组含义：dp[i][0]：没持有股票 dp[i][1]：第一次持有股票 dp[i][2]：第一次不持有股票 dp[i][3]：第二次持有股票 dp[i][4]：第二次不持有股票
2. 递推公式：见代码
3. 初始化：dp[0][0]=0 dp[0][1]=prices[0] dp[0][2]=0 dp[0][3]=prices[0] dp[0][4]=0，题目允许同一天多次买入卖出
4. 遍历顺序：从小到大

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;

        for(int i = 1; i < prices.size(); i++)
        {
            dp[i][0] = dp[i-1][0];
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i]);
            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i]);
        }

        return dp[prices.size()-1][4];
    }
};