【打卡】牛客网：BM81 买卖股票的最好时机(二)

与BM80 买卖股票的最好时机(一)的区别是，可以多次买，但是卖完才能再买。

我的想法是，对于第i天的价格，j从第0天~第i-1天的价格遍历，即，【第j天买入、今天卖出的利润】+【第j-1天的利润】，遍历，并取最大。时间复杂度是o(n^2)。

但是，我的想法出现的错误是：若第j-1天持有股，那么第j天不可以买；若不持有股，第j天可以买。

我忽略了必须卖出才能买入。

所以，必须记录第j-1天的状态是持有股，还是不持有股。但是是难实现的。

模板的：

新颖的做法（或者说，新颖的思想，因为代码和BM80差不多，只不过我在BM80的理解没有按照模板的走）。

BM80、BM81中，模板的意思：

例如，测试案例prices=[8,9,2,5,4,7,1]，分析第4天(从第0天开始数起)：

dp第0行(该天不持有股票情况的前提下，分析利润最大)：

? ? ? ? 第4天不操作，即保持dp的第0行第3天的利润。

????????第4天如果卖，那么第3天必须持有，即看dp的第1行第3天的利润。

? ? ? ? 第4天不能买，因为dp第0行是在该天不持有股票情况的前提下，分析利润最大。

dp第1行(该天持有股票情况的前提下，分析利润最大)：

? ? ? ? 第4天不操作，即保持dp的第1行第3天的利润。

????????第4天如果买，那么第3天必须不持有，即看dp的第0行第3天的利润。

? ? ? ? 第4天不能卖，因为dp第1行是在该天持有股票情况的前提下，分析利润最大。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */

    int maxProfit(vector<int>& prices) {
        // write code here
        int n = prices.size();
        if(n == 0)
            return 0;

        vector<vector<int>> dp(2, vector<int>(n));

        dp[1][0] = -prices[0]; 
        
        for(int i = 1; i < n; i++){
            dp[0][i] = max(dp[0][i-1], dp[1][i-1]+prices[i]);
            dp[1][i] = max(dp[1][i-1], dp[0][i-1]-prices[i]);
        }

        return dp[0][n-1];
    }
};