leetcode 309最佳买卖股票时机含冷冻期动态规划

深藏阁楼爱情的钟 2023-02-25 02:30 3阅读 0赞

#### 题目描述 ####

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。  
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

##### 示例: #####

输入: \[1,2,3,0,2\]  
输出: 3  
解释: 对应的交易状态为: \[买入, 卖出, 冷冻期, 买入, 卖出\]

#### 解题思路 ####

对于本题的股票买卖一共有三个状态，分别为持股，不持股处于冷冻期（前一天刚卖出股票），不持股不处于冷冻期。  
1、持股状态可能是由于之前就持有股票，或者当天买入股票(前一天不能是冷冻期)  
2、不持股处于冷冻期的状态只能由当天卖出股票所转移且第二天不能交易  
3、不持股不处于冷冻期，可以由不持股处于冷冻期或者是不持股不处于冷冻期转移得到

由此设定dp\[i\]\[3\]数组，其中i代表的是第几天，二维代表的是状态、  
列出转移方程:  
1、dp\[i\]\[0\]=max(dp\[i-1\]\[0\],dp\[i-1\]\[2\]-prices\[i\])  
2、dp\[i\]\[1\]=dp\[i-1\]\[0\]+prices\[i\]  
3、dp\[i\]\[2\]=max(dp\[i-1\]\[2\],dp\[i-1\]\[1\]);

class Solution { 
        public int maxProfit(int[] prices) { 
            int l=prices.length;
            int [][]dp=new int[l][3];
            if(l<2){ 
                return 0;
            }
            dp[0][0]=-prices[0];
            for(int i=1;i<l;i++){ 
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
                dp[i][1]=dp[i-1][0]+prices[i];
                dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]);;
            }
            return Math.max(dp[l-1][1],dp[l-1][2]);
        }
    }