LeetCode刷题--- 买卖股票的最佳时机含冷冻期

个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

?http://t.csdnimg.cn/yUl2I

【C++】? ??

??????http://t.csdnimg.cn/6AbpV

数据结构与算法

????http://t.csdnimg.cn/hKh2l

前言：这个专栏主要讲述动态规划算法，所以下面题目主要也是这些算法做的 ?

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

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

题目链接：买卖股票的最佳时机含冷冻期

题目

给定一个整数数组prices，其中第??prices[i]?表示第?i?天的股票价格 。?

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

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例 2:

输入: prices = [1]
输出: 0

提示：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

解法

算法原理讲解

我们这题使用动态规划，我们做这类题目可以分为以下五个步骤

1. 状态显示
2. 状态转移方程
3. 初始化（防止填表时不越界）
4. 填表顺序
5. 返回值

• 状态显示

• 状态转移方程

1. 处于「买?」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖出股票；
2. 处于「卖出」状态的时候：
   1. 如果「在冷冻期」，不能买?。
   2. 如果「不在冷冻期」，才能买?。

1. 在 i - 1 天持有股票，此时最?收益应该和 i - 1 天的保持?致： dp[i - 1] [0] 。
2. 在 i 天买?股票，那我们应该选择 i - 1 天不在冷冻期的时候买?，由于买?需要花钱，所以此时最大收益为： dp[i - 1][1] - prices[i]。

1. 在 i - 1 天的时候，已经处于冷冻期，然后啥也不?到第 i 天，此时对应的状态为： dp[i - 1][2] ；
2. 在 i - 1 天的时候，?上没有股票，也不在冷冻期，但是依旧啥也不?到第 i 天，此时对应的状态为 dp[i - 1][1] ；

• 初始化（防止填表时不越界）

• 填表顺序

• 返回值

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];

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

        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};