LeetCode-309. 最佳买卖股票时机含冷冻期

题目来源
309. 最佳买卖股票时机含冷冻期

题目思路

每天最多只可能有三种状态中的一种

0表示当前处于买入状态(持有股票)
1表示当前处于卖出状态(不持有股票)
2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金

            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);  //持有股票dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);  //不持有股票dp[i][2] = dp[i-1][1];  //冷冻期

dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i])意思是你只有在股票冷冻期之后才能买入
dp[i][2] = dp[i-1][1]意思是冷冻期肯定是卖出的状态(手上没有股票)

动态规划

• 1.确定dp数组以及下标的含义

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

可以定义下面三个状态
0表示当前处于买入状态(持有股票)
1表示当前处于卖出状态(不持有股票)
2表示当前处于冷冻状态 设dp[i][j]表示i - 1天状态为j时所拥有的最大现金

• 2.确定递推公式

买入状态
操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
操作二：冷冻期之后才能买 dp[i][0] = dp[i-1][2]-prices[i]
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
卖出状态
操作一：前一天就是卖出状态，dp[i][1] = dp[i - 1][1]
操作二：持有股票才能卖出，dp[i][1] = dp[i-1][0]+prices[i]
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
冷冻状态
只有卖出的状态
dp[i][2] = dp[i-1][1];

• 3.dp数组如何初始化

如果是持有股票状态那么：dp[0][0] = -prices[0]，一定是当天买入股票。
如果是不持有股票状态，dp[0][1] = 0，当天买当天卖
如果是冷冻期状态，dp[0][2] = 0,延续不持有股票的状态

• 4.确定遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

• 5.举例推导dp数组

以 [1,2,3,0,2] 为例，dp数组如下：

代码实现

class Solution {public int maxProfit(int[] prices) {if(prices == null || prices.length == 0){return 0;}int[][] dp = new int[prices.length][3];dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;for(int i = 1;i<prices.length;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);  //持有股票dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);  //不持有股票dp[i][2] = dp[i-1][1];  //冷冻期}return Math.max(dp[prices.length-1][1],dp[prices.length-1][2]);}
}