代码随想录 | Day 50 - LeetCode 123. 买卖股票的最佳时机III、LeetCode 188. 买卖股票的最佳时机IV

        今天是昨天买卖股票系列内容的延续，分别把只能买卖1次的要求扩展为2次和k次。最多买卖次数的扩展，主要反映在状态数的增多上。掌握了2次的情况之后，再来找规律就能得到k次时的解法了。

        第1题（LeetCode 123. 买卖股票的最佳时机III）相比day 49中第1题（LeetCode 121. 买卖股票的最佳时机）的改变也只有一处，这是买卖股票的最大次数，由一次变成了两次。自己没想到办法，看了题解的dp数组定义部分才有了思路，而定义部分也是这道题的核心。由于最多可以买卖两次，所以原本“持有”和“不持有”这两种状态不再够用，需要扩展为“未曾买卖”、“买过第1次”、“卖过第1次”、“买过第2次”、“买过第2次”这5种状态，第i天每个状态下能获得的最大利润对应dp[i][0]~dp[i][4]。需要再次注意这里的状态，并不一定是当天做出相应动作。如果将其命名为状态0~状态4，那么他们各自的状态转移关系如下：

• 对于状态0，其前一步只可能也是状态0，所以dp[i][0] = dp[i - 1][0]；
• 对于状态1，有可能在前一天就处于状态1（对应dp[i - 1][1]），也有可能在第i天从状态0变为状态1（dp[i - 1][0] - prices[i]），所以dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])；
• 对于状态2，有可能在前一天就处于状态2（对应dp[i - 1][2]），也有可能在第i天从状态1变为状态2（dp[i - 1][1] + prices[i]），所以dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])；
• 对于状态3，有可能在前一天就处于状态3（对应dp[i - 1][3]），也有可能在第i天从状态2变为状态3（dp[i - 1][2] - prices[i]），所以dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])；
• 对于状态4，有可能在前一天就处于状态4（对应dp[i - 1][4]），也有可能在第i天从状态3变为状态4（dp[i - 1][3] + prices[i]），所以dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])；

        初始化方面，无任何操作之前，最大利润就是0，所以dp[0][0]设置为0；第0天就处于状态1的话，只可能买入第0天的股票，所以dp[0][1] = -prices[0]；虽然第0天无法处于状态2，但一方面可以看作是第0天买入后又立即卖出，另一方面卖出时的利润都是不低于0，设置为0可以保证后面的比较大小顺利进行，所以dp[0][2] = 0；状态3同理，虽然第0天无法处于状态3，但可以看作是第0天买入再卖出后，第2次买入，所以dp[0][3] = -prices[0]；状态4与状态2同理，所以dp[0][4] = 0。由于每天的状态都依赖于前一天，所以遍历方向为正向。最终将最后一天的状态4作为结果返回。

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

         实际上，状态0的值永远是0。所以可以丢弃这一状态，然后将dp[i][1]状态转移关系里的第2部分直接改为-prices[i]。

        第2题（LeetCode 188. 买卖股票的最佳时机IV）相比上一题的改变又只有一处，就是进一步将最多买卖2次改为了k次。而总结上一题的规律，第i天的状态1~4都依赖于第(i - 1)天的当前状态和上一状态，也就是状态1~4和状态0~3。还有一处不同，就是如果某个状态对应买入，那么其状态转移关系的第2部分中，dp[i - 1][j - 1]（j代表当前状态）与prices[i]的关系就应该是相减；而如果某个状态对应卖出，那么这个关系就应该是相加。

        初始化方面也同样如此，第0天买入状态的初始化都应该是-prices[0]，卖出状态的初始化都应该是0。而在按照上一题末尾处提到的，丢弃原本的状态0，将第1次买入作为状态1的话，就能得到下面的代码。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));
        for (int j = 0; j < k; ++j) {
            dp[0][2 * j] = -prices[0];
        }
        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            for (int j = 1; j < 2 * k; ++j) {
                if (j % 2 == 1) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }
            }
        }
        return dp[prices.size() - 1][2 * k - 1];
    }
};