代码随想录51——动态规划：309最大买卖股票时机含冷冻期、714买卖股票的最大时机含手续费、300最长递增子序列

1.309最大买卖股票时机含冷冻期

参考：代码随想录，309最大买卖股票时机含冷冻期；力扣题目链接

1.1.题目

1.2.解答

这道题目复杂就复杂在冷冻期上。由于冷冻期的存在，导致持有股票的时候，如果说今天想新的买入，那么必须保证昨天是不持有股票的。但是如果不持有股票，又存在三种情况：

• 昨天刚卖出股票，此时不持有股票。但是此时今天属于冷冻期，所以无法买入股票
• 昨天是冷冻期，此时不持有股票。这样的话今天可以买入
• 昨天是冷冻期之后的天，仍然保持冷冻期的前一天卖出股票的状态，所以此时仍然是不持有股票的。这样话今天也可以买入

注意：由于卖出股票的后一天就是冷冻期，所以不持有股票是有三种状态的，分别是当天卖出股票导致不持有、前一天卖出股票今天是冷冻期导致不持有、前一天是冷冻期导致不持有。所以存在冷冻期之后，不持有股票的状态从原来的一个状态扩充成了三个状态，因此增加了难度。但是整体思路和之前的还是一样的。

直接给出代码如下。代码中dp数组的每一天有四个状态：

• 持有股票
• 不持有股票：今天刚卖出，从持有股票的状态变成不持有股票的状态
• 不持有股票：昨天刚卖出，今天是冷冻期，所以仍然是不持有股票的状态
• 不持有股票：昨天是冷冻期，今天没有任何操作，所以仍然保持不持有股票的状态

关于其中每个状态的分析，看代码中的注释即可，并不是很难。

int maxProfit(vector<int> &prices)
{
    if(prices.empty())
        return 0;
    
    // 1.定义dp数组：0123分别是持有股票、不持有(今天刚卖出)、不持有(今天冷冻期)、不持有(昨天冷冻期，今天无操作)
    vector<vector<int>> dp(prices.size(), vector<int>(4, 0));

    // 2.初始化第0天的dp数组
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    dp[0][2] = 0;
    dp[0][3] = 0;

    // 3.动态规划，使用递推公式实现
    for(int i = 1; i < prices.size(); i++)
    {
        // 1.持有股票：昨天就持有股票，或者昨天是冷冻期，今天刚买入，
        //   或者是昨天是冷冻期之后不持有，今天刚买入
        dp[i][0] = max(dp[i-1][0], max(dp[i-1][2], dp[i-1][3]) - prices[i]);

        // 2.不持有(今天刚卖出)：只能是 昨天持有股票，今天卖出
        dp[i][1] = dp[i-1][0] + prices[i];

        // 3.不持有(今天冷冻期)：只能是 昨天为冷冻期之前不持有
        dp[i][2] = dp[i-1][1];

        // 4.不持有(昨天冷冻期，今天无操作)：昨天是冷冻期，或者昨天就是冷冻期之后不持有
        dp[i][3] = max(dp[i-1][2], dp[i-1][3]);
    }

    // 最后返回结果：一定是不持有中的最大值
    return max(dp[prices.size()-1][1], max(dp[prices.size()-1][2], dp[prices.size()-1][3]));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2.714买卖股票的最大时机含手续费

参考：代码随想录，714买卖股票的最大时机含手续费；力扣题目链接

2.1.题目

2.2.解答

这道题目其实就很简单了，和没有手续费的题目求动态规划的问题一模一样，就是在不持有股票如果是今天卖出的情况，减掉手续费即可。

直接给出代码如下：

int maxProfit(vector<int> &prices, int fee)
{
    if(prices.empty())
        return 0;
    
    // 1.定义dp数组：每天要么持有股票，要么不持有股票
    vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
    
    // 2.初始化第1天的dp数组
    dp[0][0] = -prices[0];
    dp[0][1] = 0;

    // 3.动态规划：使用dp数组和递推公式
    for(int i = 1; i < prices.size(); i++)
    {
        // 1.持有股票：昨天就持有 或者 昨天不持有，今天刚买入
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);

        // 2.不持有股票：昨天就不持有 或者 昨天持有，今天卖出，注意这里有手续费！
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
    }

    // 最后返回结果，一定是不持有股票剩余的钱最多
    return dp[prices.size()-1][1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25