注册个网站多少钱,立即注册,泉州seo排名,百度推广业务电话动态规划—309. 买卖股票的最佳时机含冷冻期 题目描述前言基本思路1. 问题定义2. 理解问题和递推关系状态定义#xff1a;状态转移公式#xff1a;初始条件#xff1a; 3. 解决方法动态规划方法伪代码#xff1a; 4. 进一步优化5. 小总结 Python代码Python代码解释总结 C代… 动态规划—309. 买卖股票的最佳时机含冷冻期 题目描述前言基本思路1. 问题定义2. 理解问题和递推关系状态定义状态转移公式初始条件 3. 解决方法动态规划方法伪代码 4. 进一步优化5. 小总结 Python代码Python代码解释总结 C代码C代码解释总结 总结 题目描述 前言
最佳买卖股票时机含冷冻期问题 是一个经典的动态规划问题。给定一个数组表示股票的价格每天你只能做一件事买入股票、卖出股票或者冷冻休息。如果你在一天卖出了股票那么第二天你无法进行任何交易有一天的冷冻期。目标是通过买卖股票来获得最大的收益。该问题要求我们结合动态规划的思想合理规划买卖操作以获取最大的利润。 基本思路
1. 问题定义
给定一个数组 prices其中 prices[i] 表示第 i 天的股票价格。你可以在任意天选择买入或卖出股票但在卖出股票后的第二天不能买入有一天冷冻期。目标是找到能够获得的最大利润。
2. 理解问题和递推关系
为了帮助我们理解该问题的动态规划思路我们可以定义几种状态来表示我们在某一天的持有情况。主要有以下三种状态
状态定义 持有股票的状态hold hold[i] 表示在第 i 天结束时我们持有股票时的最大收益。这个状态可以从两种情况转移而来要么是之前买入并继续持有hold[i-1]要么是今天刚刚买入。 未持有股票且处于冷冻期的状态cooldown cooldown[i] 表示在第 i 天结束时我们处于冷冻期时的最大收益也就是说第 i 天刚卖出股票不能买入股票。这个状态只能通过在 i 天卖出股票后进入因此 cooldown[i] hold[i-1] prices[i]。 未持有股票且不处于冷冻期的状态sell sell[i] 表示在第 i 天结束时我们没有持有股票且没有处于冷冻期的最大收益。这个状态有两种来源要么是处于冷冻期后过了一天cooldown[i-1]要么是之前一直不持有股票sell[i-1]。
状态转移公式 hold[i] max(hold[i-1], sell[i-1] - prices[i]) 要么我们继续持有股票要么我们在第 i 天买入股票。 cooldown[i] hold[i-1] prices[i] 表示我们在第 i 天卖出了股票进入冷冻期。 sell[i] max(sell[i-1], cooldown[i-1]) 表示我们处于不持有股票且不在冷冻期的状态可以是冷冻期结束或者一直未持有股票。
初始条件
hold[0] -prices[0]表示在第 0 天买入股票的收益。sell[0] 0在第 0 天不持有股票收益为 0。cooldown[0] 0在第 0 天没有冷冻期收益为 0。
3. 解决方法
动态规划方法
定义 hold[i]cooldown[i] 和 sell[i] 来表示每一天的三种状态的最大收益。使用递推公式更新这三种状态的值。最终结果为 max(sell[n-1], cooldown[n-1])即在最后一天没有持有股票时的最大收益。
伪代码
initialize hold[0] -prices[0], sell[0] 0, cooldown[0] 0
for each day i from 1 to n-1:hold[i] max(hold[i-1], sell[i-1] - prices[i])cooldown[i] hold[i-1] prices[i]sell[i] max(sell[i-1], cooldown[i-1])
return max(sell[n-1], cooldown[n-1])4. 进一步优化
空间优化由于 dp[i] 仅依赖于 dp[i-1]我们可以将动态规划中的 hold、cooldown 和 sell 状态用常量来代替从而将空间复杂度优化到 O(1)。
5. 小总结
问题思路通过将状态分为持有股票、未持有且处于冷冻期、未持有且不在冷冻期三种情况动态规划可以清晰地描述问题的状态转移过程。时间复杂度该算法的时间复杂度为 O(n)空间复杂度可以优化为 O(1)。
以上就是买卖股票的最佳时机含冷冻期问题的基本思路。 Python代码
class Solution:def maxProfit(self, prices: list[int]) - int:if not prices:return 0n len(prices)# 初始化第0天的状态hold -prices[0]sell 0cooldown 0for i in range(1, n):# 更新状态new_hold max(hold, sell - prices[i])new_cooldown hold prices[i]new_sell max(sell, cooldown)# 更新hold, cooldown, sellhold, cooldown, sell new_hold, new_cooldown, new_sell# 返回sell和cooldown中的较大值return max(sell, cooldown)Python代码解释总结
初始化在第 0 天如果持有股票则收益为 -prices[0]否则为 0。状态转移通过递推公式更新每一天的 hold、cooldown 和 sell 状态。返回结果在最后一天返回不持有股票状态下的最大收益即 max(sell, cooldown)。 C代码
#include vector
#include algorithm
using namespace std;class Solution {
public:int maxProfit(vectorint prices) {if (prices.empty()) return 0;int n prices.size();// 初始化第0天的状态int hold -prices[0];int sell 0;int cooldown 0;for (int i 1; i n; i) {// 更新状态int new_hold max(hold, sell - prices[i]);int new_cooldown hold prices[i];int new_sell max(sell, cooldown);// 更新hold, cooldown, sellhold new_hold;cooldown new_cooldown;sell new_sell;}// 返回sell和cooldown中的较大值return max(sell, cooldown);}
};C代码解释总结
初始化在第 0 天如果持有股票则收益为 -prices[0]否则为 0。状态转移通过递推公式更新每一天的 hold、cooldown 和 sell 状态。返回结果在最后一天返回不持有股票状态下的最大收益即 max(sell, cooldown)。 总结
核心思想通过将买卖股票问题划分为持有股票、未持有且处于冷冻期、未持有且不在冷冻期三种状态动态规划可以清晰地模拟问题的状态转移过程。时间复杂度该算法的时间复杂度为 O(n)可以处理大规模的输入。空间优化由于每个状态只依赖前一天的状态空间复杂度可以从 O(n) 优化为 O(1)。
