LeetCode123：买卖股票的最佳时机III

题目链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i][0]不操作
        //dp[i][1]第一次持有股票的最大现金
        //dp[i][2]第一次不持有股票的最大现金
        //dp[i][3]第二次持有股票的最大现金
        //dp[i][4]第二次不持有股票的最大现金
        if(prices.size() == 0)  return 0;
        vector<vector<int> > dp(prices.size() + 1, 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];
    }
};

这个题目其实我们要把他分成二次的嘛，每一次再细分成持有股票和不持有股票，然后就开始取初始化这个数字，用二位数组来定义这个状态。

递推公式：

dp[i][0] = dp[i - 1][0];

这个就是不持有，那我i - 1天都不持有呗
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

这个就是要去取一个最大值了，那我要是当前持有的话，就要分两种情况，第一种是我之前就已经持有了，dp[i - 1][1]， 第二个情况就是我之前就不持有，但我买了，所以就要不持有减去我买了股票的现金数，也就是 d p[i - 1][0] - prices[i]
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);

这个也是分两种情况，那我不持有，分两种情况，不持有的话那我之前就可能不持有，所以是dp[i - 1][2], 另一种情况是之前持有，所以我就要卖出去这个股票了，那我就要加上我当时卖出股票的钱。
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]);

以此类推

初始化：

dp[0][0] = 0;

我当前不持有，那我现金肯定是0
dp[0][1] -= prices[0];

这个是我当前持有的，所以要买这个股票，要减去价钱
dp[0][2] = 0;

这个是我当前不持有股票的，也就是我卖出去了，这个时候就要加上prices[i]了，但是你想想，既然要卖，那我肯定是不能赔，那么我的利润一定是大于等于0，所以初始化为0
dp[0][3] -= prices[0];

以此类推
dp[0][4] = 0;

以此类推

遍历顺序：从1开始，因为初始化0了

返回值：为什么是返回dp[price.size() - 1][4]呢，因为你想想，你之前的第一次不持有，也就是第一次赚的利润，拿到第二次用了，也就是一个连贯了，所哟dp[price.size()][4]内部就是两次利润的总和了。

原文地址：https://blog.csdn.net/Ricky_youngone/article/details/143027113

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！