动态规划：买卖股票的最佳时期含冷冻期

本文主要是介绍动态规划：买卖股票的最佳时期含冷冻期，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

题目

思路 

解题过程

复杂度 

code

---

题目

        给定一个整数数组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. 定义状态：设dp[i][0]表示到第i天为止不持有股票可以获得的最大利润，dp[i][1]表示到第i天为止持有股票可以获得的最大利润。

2. 状态转移方程：

   

3. 初始化：dp[0][0] = 0，表示在第一天开始时不持有股票的利润是0；dp[0][1] = -prices[0]，表示在第一天买入股票的利润是负的。

4. 计算顺序：从第1天开始，根据前一天或前两天的状态来更新当前天的状态。

5. 构造最优解：dp[n-1][0]将给出最后一天结束时不持有股票可以获得的最大利润。

---

复杂度 

• 时间复杂度：O(n)，其中n是数组prices的长度。
• 空间复杂度：O(n)，用于存储动态规划表。

---

code

class Solution(object):def maxProfit(self, prices):n = len(prices)if n < 2:return 0# 初始化动态规划表dp = [[0, 0] for _ in range(n)]# 第一天的情况dp[0][1] = -prices[0]for i in range(1, n):# 状态转移：卖出股票dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])# 状态转移：买入股票，考虑冷冻期if i > 0:dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])return dp[-1][0]

这篇关于动态规划：买卖股票的最佳时期含冷冻期的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---