目录

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

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

题目

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题题目可以分析从出以下几个信息
1.交易次数无限次
2.买入条件做了限制，必须停一天才能买

dp数组及其下标的含义
状态还是持有与不持有两个状态，交易次数没限制，那么我们可以按照之前的办法定义dp数组

dp[i][0]:表示第i天不持有状态下的最大利润
dp[i][1]:表示第i天持有状态下的最大利润

确定递推式

如果第i天是不持有状态

• 如果第i天没有执行操作，dp[i][0] = dp[i-1][0]
• 如果第i天执行了卖出操作，dp[i][0] = dp[i-1][1] + prices[i]
  dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])

如果第i天持有状态

• 如果第i天没有执行操作，dp[i][1] = dp[i-1][1]
• 如果第i天执行了买入操作，dp[i][1] = dp[i-2][0] - prices[i]
  dp[i][1] = Math.max( dp[i-1][1],dp[i][1] = dp[i-2][0] - prices[i])

dp数组初始化

dp[0][0]=0
dp[0][1]= -prices[0]
dp[1][1]= Math.max(-prices[0],-prices[1])
dp[1][0]= Math.max(0,prices[1]-prices[0])

遍历顺序
从小到大遍历

dp[0][0]=0
dp[0][1]= -prices[0]
dp[1][1]= Math.max(-prices[0],-prices[1])
dp[1][0]= Math.max(0,prices[1]-prices[0])
for(int i=2;i<prices.length;i++){
	dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
	dp[i][1] = Math.max( dp[i-1][1],dp[i-2][0] - prices[i]);
}

举例推理dp数组
假设prices= [1,2,3,0,2]

代码

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