最小成本爬楼梯（Minimum Cost Climbing Stairs）的变种：带冷却时间的最小成本爬楼梯
题目描述
你正在爬楼梯。楼梯有 n 个台阶，用数组 cost 表示，cost[i] 表示踏上第 i 个台阶需要支付的成本（索引从 0 开始）。你每次可以向上爬 1 个台阶 或 2 个台阶，但有一个额外限制：
- 如果你从第
i个台阶向上爬了 2 个台阶（即从i到i+2），那么踏上第i+2个台阶后，你必须 跳过下一个台阶（即不能从i+2直接到i+3，必须从i+2跳到i+4或更远）。
换句话说，每次跳 2 个台阶会触发一个“冷却”效果，迫使你在下一个选择中至少跳 2 个台阶。
你的目标是到达 第 n 个台阶之后（即索引 n 或 n+1，只要超出最后一个台阶即可），求出需要支付的 最小总成本。初始时你可以从 下标 0 或 下标 1 的台阶开始，且初始选择不触发冷却。
示例
n = 5, cost = [1, 100, 1, 1, 1, 100]
- 从下标 0 开始，支付 1，跳到 2（跳 2 阶，触发冷却），支付 1，从 2 到 4（必须跳 2 阶，因为冷却中），支付 1，到达终点（超过下标 5）。总成本 = 1 + 1 + 1 = 3。
- 从下标 1 开始，支付 100，跳到 3（跳 2 阶，触发冷却），支付 1，从 3 到 5（必须跳 2 阶），支付 100，总成本 = 100 + 1 + 100 = 201。
- 最优解是 3。
解题思路
这是一个线性动态规划问题，需要在经典“最小成本爬楼梯”上增加状态，以记录“是否处于冷却时间”。
1. 定义状态
设：
dp[i][0]= 到达第i个台阶，且不处于冷却状态（即上一步不是跳 2 阶）的最小成本。dp[i][1]= 到达第i个台阶，且处于冷却状态（即上一步跳了 2 阶）的最小成本。
冷却状态的含义：
如果到达 i 时状态为 1（冷却），那么从 i 出发时，只能跳 2 个台阶（因为必须跳过下一个台阶）。
如果状态为 0（非冷却），则可以从 i 跳 1 阶或 2 阶。
注意：cost[i] 是踏上第 i 阶时支付的，不是离开时支付。
2. 状态转移
我们考虑如何到达 i。
(1) 到达 i 时处于非冷却状态（dp[i][0]）：
这意味着上一步是跳 1 阶来的，因为如果上一步跳 2 阶，现在就会处于冷却状态。
所以上一步在 i-1，并且上一步的状态可以是 0 或 1（因为在 i-1 时是否冷却不影响这一步，只要这一步只跳 1 阶就不会触发冷却）。
但是注意：从 i-1 到 i 是跳 1 阶，不会触发冷却，所以 i-1 的状态任意。
转移方程：
\[dp[i][0] = \min(dp[i-1][0],\; dp[i-1][1]) + cost[i] \]
(2) 到达 i 时处于冷却状态（dp[i][1]）：
这意味着上一步是跳 2 阶来的，并且触发冷却。
所以上一步在 i-2，并且从 i-2 到 i 跳了 2 阶。
因为跳 2 阶触发冷却，所以 i-2 的状态必须是非冷却（如果 i-2 已经是冷却状态，则不能从那里跳 2 阶，因为连续两次跳 2 阶会导致跳过中间台阶的规则冲突？我们需要明确：题目只说“跳 2 阶”触发冷却，并没有禁止连续两次跳 2 阶，但若从冷却状态跳 2 阶，其实已经满足“跳过下一个台阶”的要求，因为冷却状态本就要求下一步必须至少跳 2 阶。
仔细分析：
- 如果
i-2是冷却状态，则从i-2出发必须跳 2 阶，这正好满足跳 2 阶的动作，所以允许。
但是跳 2 阶后到达i，又会触发新的冷却。
所以状态转移是允许从dp[i-2][1]来的。
但这里需要注意：从 i-2 出发跳 2 阶，无论 i-2 原来是什么状态，都会使到达 i 时处于冷却状态。
所以：
\[dp[i][1] = \min(dp[i-2][0],\; dp[i-2][1]) + cost[i] \]
等等，这里有个细节：如果 i-2 是冷却状态，则从 i-2 出发只能跳 2 阶，这符合要求，所以可以从 dp[i-2][1] 转移。
但题目要求是“踏上第 i+2 个台阶后，必须跳过下一个台阶”，这意味着在 i 是冷却状态时，从 i 出发的下一步必须跳 2 阶，这已经体现在我们设计状态中，不影响从哪来的问题。
所以转移方程是：
\[dp[i][1] = \min(dp[i-2][0],\; dp[i-2][1]) + cost[i] \]
3. 初始化
我们可以在 cost 数组前面添加两个虚拟台阶 -2 和 -1，对应起点之前的两个位置，成本为 0，并且状态为 0（非冷却），因为一开始没有跳过 2 阶。
更方便的做法是直接初始化：
- 可以从下标 0 或 1 开始，初始时不在冷却。
定义dp[0][0] = cost[0],dp[0][1] = 无穷大（不可能一开始就冷却）。
dp[1][0] = cost[1],dp[1][1] = cost[1]? 不对，到达 1 时冷却意味着是从 -1 跳 2 阶来的，但 -1 不存在。所以dp[1][1] = 无穷大。
更系统地，我们定义：
\[dp[0][0] = cost[0],\quad dp[0][1] = \infty \]
\[ dp[1][0] = cost[1],\quad dp[1][1] = \infty \]
然后从 i=2 开始递推。
4. 最终目标
我们需要到达第 n 个台阶之后。
即最终位置可以是 n 或 n+1。
但我们的 dp 只到 n-1（因为 cost 长度 n）。
所以我们最后看：
到达 n 的最小成本 = 从 n-1 跳 1 阶 或 从 n-2 跳 2 阶。
但注意：如果从 n-1 跳 1 阶，则要求 n-1 的状态任意，不会触发冷却（因为已经结束）。
如果从 n-2 跳 2 阶，会触发冷却，但冷却只影响后续步骤，我们已经结束，所以没关系。
更简单：我们可以在 cost 后面添加一个 0 作为终点，然后求到终点的最小成本。
但题目是“到达顶部”，即超过最后一个台阶，可以认为 cost[n] = 0。
所以我们扩展 cost 长度到 n+1，cost[n] = 0，然后求 dp[n][0] 和 dp[n][1] 的最小值。
逐步递推
用示例 cost = [1, 100, 1, 1, 1, 100]，我们在最后加 0 变成 [1, 100, 1, 1, 1, 100, 0]，n=6（索引 0~6）。
初始化：
dp[0][0] = 1, dp[0][1] = INF
dp[1][0] = 100, dp[1][1] = INF
i=2:
dp[2][0] = min(dp[1][0], dp[1][1]) + cost[2] = min(100, INF) + 1 = 101
dp[2][1] = min(dp[0][0], dp[0][1]) + cost[2] = min(1, INF) + 1 = 2
i=3:
dp[3][0] = min(dp[2][0], dp[2][1]) + 1 = min(101, 2) + 1 = 3
dp[3][1] = min(dp[1][0], dp[1][1]) + 1 = min(100, INF) + 1 = 101
i=4:
dp[4][0] = min(dp[3][0], dp[3][1]) + 1 = min(3, 101) + 1 = 4
dp[4][1] = min(dp[2][0], dp[2][1]) + 1 = min(101, 2) + 1 = 3
i=5:
dp[5][0] = min(dp[4][0], dp[4][1]) + 100 = min(4, 3) + 100 = 103
dp[5][1] = min(dp[3][0], dp[3][1]) + 100 = min(3, 101) + 100 = 103
i=6 (终点，cost=0):
dp[6][0] = min(dp[5][0], dp[5][1]) + 0 = min(103, 103) = 103
dp[6][1] = min(dp[4][0], dp[4][1]) + 0 = min(4, 3) = 3
结果 = min(dp[6][0], dp[6][1]) = 3，与示例一致。
算法总结
- 在 cost 末尾添加 0，表示终点台阶成本为 0。
- 初始化 dp[0][0]=cost[0], dp[0][1]=INF, dp[1][0]=cost[1], dp[1][1]=INF。
- 从 i=2 到 n：
- dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + cost[i]
- dp[i][1] = min(dp[i-2][0], dp[i-2][1]) + cost[i]
- 答案是 min(dp[n][0], dp[n][1])。
时间复杂度 O(n)，空间复杂度 O(n)，可优化到 O(1)。
关键点
- 冷却状态的定义：表示当前台阶必须跳 2 阶离开。
- 状态转移时，从冷却状态出发只能跳 2 阶，所以它只影响“去向”，不影响“来源”。
- 初始化时，前两个台阶不可能处于冷却状态（因为没有前两步跳 2 阶）。
- 扩展一个零成本终点台阶，统一处理终点。