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

题目来源

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

题目详情

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

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

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

示例:

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

题解分析

解法一：动态规划

1. 本题是买卖股票问题的变种，其他相关的问题还有：
   • 121.买卖股票的最佳时机
   • 122.买卖股票的最佳时机 II
   • 123.买卖股票的最佳时机 III
   • 188.买卖股票的最佳时机 IV
   • 309.最佳买卖股票时机含冷冻期
   • 714.买卖股票的最佳时机含手续费
   • 剑指 Offer 63. 股票的最大利润
2. 这题买卖股票的解法可以使用动态规划的思想来做，首先考虑到有买入卖出以及冻结期，看似是一个十分复杂的问题，确实它的动态状态转换也有一定难度。
3. 根据题意，可以将某一个时刻的状态划分为三种：持股，空股且处于冻结期，空股但处于非冻结期。分别使用dp[i][0],dp[i][1],dp[i][2]来表示。
4. 对于dp[i][0]，这个状态可以由max(dp[i-1][0], dp[i-1][2] - prices[i])转换而来。这里可以进行的操作是，要么继续持股，要么在第i天买入一直股票，这要求前一天处于空股且非冻结状态。
5. 对于dp[i][1]，它的状态可以直接由dp[i-1][0] + prices[i]状态转换而来，这个状态只能由第i天卖出一支股票来转移。
6. 对于dp[i][2]，它的状态转移方程为：max(dp[i-1][1], dp[i-1][2])，即从空股状态转换而来，因为要求这次处于非冻结状态，所以这一天不可以买卖股票。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][]dp = new int[n][3];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        for(int i=1; i

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int pre0 = -prices[0];
        int pre1 = 0;
        int pre2 = 0;
        for(int i=1; i