LeetCode题解系列--309. Best Time to Buy and Sell Stock with Cooldown

描述

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

题意梗概

这题还是股票系列的续集，不同的是加入了条件冷却，在售出后的一天不能购买股票，需要隔一天才能购买股票，我没想出太好的解决方案，参考了discussion里的一些思路解答出此题。

思路

使用有限状态机+DP思考
这题对于每一天有三种状态：

• S0:手中未持有，可以购买
• S1:手中持有一股，可以出售
• S2:手中未持有，不能购买
  状态转移情况如下：
  

对于那些可以由两个以上状态转移得到的状态，我们进行最优化选择（可能就是DP

解答

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 1) {
            return 0;
        }
        int n = prices.size();
        // no stock on hand, can buy
        vector<int> s0(n, 0);
        // one stock on hand, can sell
        vector<int> s1(n, 0);
        s1[0] = -prices[0];
        // no stock on hand, need rest, can not buy
        vector<int> s2(n, 0);
        for (int i = 1; i < n; ++i) {
            s0[i] = max(s0[i - 1], s2[i - 1]);
            s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]);
            s2[i] = s1[i - 1] + prices[i];
        }
        return max(s0[n - 1], s2[n - 1]);
    }
};