本文主要是介绍动态规划：买卖股票的最佳时期含冷冻期，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
题目
思路
解题过程
复杂度
code
题目
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
思路
这个问题可以通过动态规划解决，但需要考虑“冷冻期”的约束。我们可以定义两个状态数组，一个表示持有股票的最大利润，一个表示不持有股票的最大利润。
解题过程
-
定义状态：设
dp[i][0]表示到第i天为止不持有股票可以获得的最大利润，dp[i][1]表示到第i天为止持有股票可以获得的最大利润。 -
状态转移方程：
-
初始化：
dp[0][0] = 0，表示在第一天开始时不持有股票的利润是0；dp[0][1] = -prices[0]，表示在第一天买入股票的利润是负的。 -
计算顺序：从第1天开始，根据前一天或前两天的状态来更新当前天的状态。
-
构造最优解：
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]这篇关于动态规划：买卖股票的最佳时期含冷冻期的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
