【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 买卖股票的最佳时机含冷冻期（难度⭐⭐）（79）

本文主要是介绍【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 买卖股票的最佳时机含冷冻期（难度⭐⭐）（79），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目解析

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

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

二、算法思路

1. 状态表示

• dp[i][0]：表示第 i 天结束后，处于「买入」状态（即持有股票）时的最大利润。
• dp[i][1]：表示第 i 天结束后，处于「可交易」（即不持有股票且不在冷冻期）状态时的最大利润。
• dp[i][2]：表示第 i 天结束后，处于「冷冻期」状态时的最大利润。

2. 状态转移方程

• dp[i][0] 的转移：
  • 要么在 i-1 天已经持有股票（即 dp[i-1][0]）。
  • 要么在 i 天买入股票（需确保 i-1 天不在冷冻期，即 dp[i-1][1] - prices[i]）。
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
• dp[i][1] 的转移：
  • 要么在 i-1 天处于冷冻期（即 dp[i-1][2]）。
  • 要么在 i-1 天就没有股票且不在冷冻期（即 dp[i-1][1]）。
  • dp[i][1] = max(dp[i-1][1], dp[i-1][2])
• dp[i][2] 的转移：
  • 只能在 i-1 天卖出股票后进入冷冻期（即 dp[i-1][0] + prices[i]）。
  • dp[i][2] = dp[i-1][0] + prices[i]

3. 初始化

• dp[0][0]：第一天买入股票，所以 dp[0][0] = -prices[0]。
• dp[0][1] 和 dp[0][2]：第一天无法卖出或进入冷冻期，所以均为 0。

4. 填表顺序

• 按照天数 i 从 1 到 n-1 遍历，并填充 dp 数组。

5. 返回值

• 最终答案应为最后一天处于「可交易」或「冷冻期」状态时的最大利润，即 max(dp[n-1][1], dp[n-1][2])。

3.代码编写

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]);}
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~

这篇关于【Leetcode每日一题】 动态规划 - 简单多状态 dp 问题 - 买卖股票的最佳时机含冷冻期（难度⭐⭐）（79）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---