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

原题链接： https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

Buy and Sell Stock专题相关题目

121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
309. Best Time to Buy and Sell Stock with Cooldown
714. Best Time to Buy and Sell Stock with Transaction Fee

1. 题目简介

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)

给出一个数组，代表着某支股票在第 i 天的价格，需要输出股票交易可获得的最大利润。可以不限次数买卖股票，但是必须先买后卖，每次交易不能再同一时刻。
最重要的是，在卖出股票后，不能在下一天买股票。

Example:

Input: [1,2,3,0,2]
Output: 3 
Explanation: transactions = [buy, sell, cooldown, buy, sell]

2. 题目解法

动态规划法 - 结合有限状态机

这个题非常特殊，使用了一种结合有限状态机的动态规划。

注： 本解法的图片和思路来自 https://blog.csdn.net/lujie1996/article/details/80281564

步骤1：构造有限状态机

在本题中，每当遇到第 i 天的股票时，有三个状态：
S0：没有买，也没有卖。
S1：买了股票，但是还没有卖出
S1：卖出了股票，但是处于Cooldown状态，此时是不能买股票的。

这几个状态之间的转化关系如下图所示，共有三个状态，五条边，每天都必须走一条边。

每个边的含义是：

S0 -> S1：今天购入股票；
S0 -> S0： 等待，不购入股票；
S1 -> S1：购入股票后等待，不售出股票；
S1 -> S2： 将持有的股票售出；
S2 -> S0：售出股票之后，熬过了cooldown期，进入可以再次购买的状态。

步骤2：寻找递推关系

有三个数组s0[], s1[], s2[]，表示的是在第 i 天到达时，若处于该状态时可以获得的最大收益。

s0[i] = max(s0[i - 1], s2[i - 1]);
// 继续在s0，或者从s2结束cooldown期转移到s0

s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]);
// 继续持有股票不卖出，或者卖出第i天的股票

s2[i] = s1[i - 1] + prices[i]; 
// s2代表刚刚卖出股票，需要加上卖出股票获得的收益

按照上述递归公式，可以很快写出成功实现的代码

实现代码

class Solution {
  public int maxProfit(int[] prices) {

        int length = prices.length;
        if(prices == null || length == 0) {
        	return 0;
        }
        
        int [] s0 = new int [length];
        int [] s1 = new int [length];
        int [] s2 = new int [length];
        
        s0[0] = 0;
        s1[0] = 0- prices[0];
        s2[0] = Integer.MIN_VALUE;
        
        for (int i = 1; i < length; i++) {
    		s0[i] = Math.max(s0[i - 1], s2[i - 1]);
    		s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
    		s2[i] = s1[i - 1] + prices[i];
    	}
  
        return Math.max(s0[length - 1], s2[length - 1]);
    }
}

步骤3：进一步优化

这里面的s0、s1、s2在更新[ i ]的时候都只用到了 [i-1] 的值，因此可以使用三个数来代替三个数组，节省空间。

class Solution {
  public int maxProfit(int[] prices) {
  
        int length = prices.length;
        if(prices == null || length == 0) {
        	return 0;
        }
       
        int s0 = 0;
        int s1 = 0- prices[0];
        int s2 = Integer.MIN_VALUE;
        
        int temp_s0 = 0;
        int temp_s1 = 0;
        
        for (int i = 1; i < length; i++) {	
        	temp_s0 = s0;
        	temp_s1 = s1;
    		s0 = Math.max(s0, s2);
    		s1 = Math.max(s1, temp_s0 - prices[i]);
    		s2 = temp_s1 + prices[i];
    	}
        return Math.max(s0, s2);
    }
}

3. 参考资料

https://blog.csdn.net/lujie1996/article/details/80281564