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:
1
2
3
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

[leetcode 309] Best Time to Buy and Sell Stock with Cooldown

参见Share my DP solution (By State Machine Thinking)
该题目有三个过程，一个是空闲状态，记为s0；一个是买入状态，记为s1；一个是卖出状态，记为s2；如下图所示：

用三个数组来记录每一时刻的变化，用s0[i]表示对于第i个时刻，空闲状态的最大值，要么是前一个s0[i-1](继续空闲)，要么是前一个s2[i-1](卖出后，就回到了空闲状态)；用s1[i]表示对于第i个时刻，买入状态的最大值，要么是前一次买入该次不做任何变化，即s1[i-1]，要么是空闲状态买入，即s0[i-1]-prices[i]；用s2[i]表示对于第i个时刻，卖出的情况，即s1[i-1]+prices[i]。【这里说一下，一定要按照状态机的思想去理解这些，而不是思考代码前后关系】，这样有如下公式：

1
2
3

s0[i] = max(s0[i - 1], s2[i - 1]); // Stay at s0, or rest from s2
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // Stay at s1, or buy from s0
s2[i] = s1[i - 1] + prices[i]; // Only one way from s1

这里我将代码简化了一下，不需要用数组，因为只需要知道前一个即可，代码如下：

public static int maxProfit(int[] prices) {
    if(prices==null||prices.length<=1)return 0;
    int s0,s1,s2;
    s0=0;
    s1=-prices[0];
    s2=0;
    for(int i=1;i<prices.length;i++){
        int temp0=s0,temp1=s1;
        s0=Math.max(s0,s2);
        s1=Math.max(s1,temp0-prices[i]);
        s2=temp1+prices[i];
    }
    return Math.max(s0,s2);
}