day163—递归—买卖股票的最佳时机含冷冻期（LeetCode-309）
题目描述
给定一个整数数组prices，其中第prices[i]表示第i天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入:prices = [1,2,3,0,2]输出:3解释:对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入:prices = [1]输出:0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
解决方案：
这段代码是基于记忆化递归求解 “含冷冻期的股票买卖最佳时机” 问题（买入股票后需隔至少一天才能再次操作，即卖出后次日不能买入），在原有无限次交易递归逻辑的基础上，仅修改了 “买入” 操作的前驱状态，适配了冷冻期规则，同时保留记忆化优化以解决超时 / 栈溢出问题。
核心逻辑
核心定义：
memo：二维记忆化数组（len×2），memo[end][0/1]缓存dfs(end, is)的结果（0 = 不持有股票，1 = 持有股票），避免重复递归；dfs(end, is, nums)：返回从第 0 到第end天，在is状态（true= 持有、false= 不持有）下能获得的最大利润，且满足 “冷冻期” 规则。
递归边界：
- 当
end < 0（所有天数遍历完毕）：- 若
is=true（仍持有股票），返回-0xFFFF（极小值，代表非法状态）； - 若
is=false（不持有股票），返回 0（无交易时利润为 0）。
- 若
- 当
记忆化优化：计算
dfs(end, is)前，先检查memo[end][state]（state为 0/1 对应不持有 / 持有），若不为 - 1 则直接返回缓存值，避免重复递归，时间复杂度从O(2n)降至O(n)。状态转移（核心：适配冷冻期）：
- 持有股票（is=true）：代表第
end天买入了股票，因冷冻期规则，买入前必须保证第end-1天不操作（即前驱状态为end-2天不持有），因此利润取：- 继续持有：
dfs(end-1, true, nums)（第end天不操作，保持持有）； - 买入股票：
dfs(end-2, false, nums) - nums[end]（第end天买入，成本为nums[end]，且前驱是end-2天不持有，规避冷冻期）； - 最终取两者最大值。
- 继续持有：
- 不持有股票（is=false）：代表第
end天卖出或不操作，无冷冻期限制，利润取：- 继续不持有：
dfs(end-1, false, nums)（第end天不操作）； - 卖出股票：
dfs(end-1, true, nums) + nums[end]（第end天卖出，收益为nums[end]）； - 最终取两者最大值。
- 继续不持有：
- 持有股票（is=true）：代表第
主函数逻辑：初始化记忆化数组，调用
dfs(len-1, false, prices)（从最后一天、不持有股票的初始状态开始计算），返回符合冷冻期规则的最大利润。
关键特点
- 规则适配：仅修改 “买入” 操作的前驱状态为
end-2，精准适配 “卖出后次日不能买入” 的冷冻期规则； - 效率优化：记忆化缓存解决了纯递归的超时 / 栈溢出问题，能处理大数据量用例；
- 逻辑兼容：保留原有递归框架，仅最小化修改核心状态转移，易理解、易维护。
总结
- 核心思路：在记忆化递归的基础上，通过调整 “买入” 操作的前驱状态（从
end-1改为end-2），适配股票买卖的冷冻期规则； - 关键设计：
memo数组缓存状态结果是效率核心，end-2的前驱状态是冷冻期规则的核心体现； - 功能效果：能正确计算含冷冻期的股票最大利润，稳定通过大数据量用例。
函数源码：
class Solution { public: vector<vector<int>> memo; // 仅修改该函数：增加记忆化+修正状态转移符号+规范边界值 int dfs(int end, bool is, vector<int>& nums) { int len = nums.size(); if(end < 0) { // 边界值修正：用INT_MIN表示持有股票的非法状态，更规范 if(is) return -0xFFFF; return 0; } int state = is ? 1 : 0; // 0=不持有，1=持有 if (memo[end][state] != -1) { return memo[end][state]; } int res; if(is) { res = max(dfs(end-1, true, nums), dfs(end-2, false, nums) - nums[end]); } else { res = max(dfs(end-1, false, nums), dfs(end-1, true, nums) + nums[end]); } // 缓存当前状态的结果 return memo[end][state] = res; } int maxProfit(vector<int>& prices) { int len = prices.size(); if (len == 0) return 0; // 空数组边界处理 // 初始化记忆化数组（len行2列，初始值-1表示未计算） memo.assign(len, vector<int>(2, -1)); // max(0, ...) 确保利润不会为负（无交易时利润为0） return dfs(len-1, false, prices); } };