力扣 每日一題 309. 最佳買賣股票時機含冷凍期

題目

給定一個整數數組，其中第 i 個元素代表了第 i 天的股票價格 。​

設計一個算法計算出最大利潤。在滿足以下限制條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:

你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票

）。

賣出股票後，你無法在第二天買入股票 (即冷凍期為 1 天)。

示例:

輸入: [1,2,3,0,2]

輸出: 3 

解釋: 對應的交易狀态為: [買入, 賣出, 冷凍期, 買入, 賣出]

題解

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        int[][] dp = new int[prices.length][3];  // dp[i][x]第i天進入x狀态(0.不持股，1.持股，2.冷凍期)
        dp[0][0] = 0;   //不持股
        dp[0][1] = -prices[0];  //持股
        dp[0][2] = 0;   //冷凍期
        for(int i= 1; i < prices.length; i++){
            //第i天不持股可以從兩種狀态轉移而來，1.第i-1天不持股，今天仍不買股票，保持不持股狀态。2.冷凍期結束了，但是今天不買股票。
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
            //第i天持股可以從兩種狀态轉移來，1.第i-1天不持股，今天買過，2.第i-1天持股，今天不賣出
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            //隻有第i天賣出了股票，第i天才能進入冷凍期。
            dp[i][2] = dp[i - 1][1] + prices[i];
        }
        // 隻有最後一天不持股或者前一天賣掉了這兩種情況手裡拿着錢，最大值在兩者中産生
        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][2]);
    }
}