线性动态规划：最小花费爬楼梯的变种——带冷却时间的最小花费爬楼梯

字数 2490 2025-11-07 12:32:50

线性动态规划：最小花费爬楼梯的变种——带冷却时间的最小花费爬楼梯

题目描述
假设你正在爬楼梯。楼梯共有 n 阶，每次你可以爬 1 阶或 2 阶，但每次爬完 2 阶后，必须等待一个冷却时间（即下一步不能立即爬，需要跳过一步）。每阶楼梯有一个非负体力花费值 cost[i]（从索引 0 开始），你每爬到一阶楼梯就要支付对应的花费。求从地面（起点，在楼梯底部）爬到楼梯顶部（即越过最后一阶楼梯）的最小总花费。注意：起点和终点均不收取花费。

示例
输入：cost = [10, 15, 20, 10, 5]
输出：25
解释：路径为：起点 → 第2阶（花费15）→ 冷却（跳过第3阶）→ 第4阶（花费10）→ 终点。总花费为 15 + 10 = 25。

解题过程

步骤1：理解问题与状态定义

冷却时间规则：若当前爬了 2 阶，下一步必须跳过一阶（即冷却一阶）。
目标：最小化总花费，且起点和终点无花费。
关键点：需要记录前一步是否爬了 2 阶，以决定当前能否行动。

定义状态：
设 dp[i][j] 表示到达第 i 阶楼梯时的最小累计花费，其中 j 表示前一步的跳跃类型：

j = 0：前一步爬了 1 阶（无冷却限制，下一步可爬1或2阶）。
j = 1：前一步爬了 2 阶（处于冷却期，下一步只能爬1阶，且跳过当前阶）。

注意：i 从 0 开始（第0阶对应第一阶楼梯），终点为 n（即越过第 n-1 阶）。

步骤2：状态转移方程
考虑从第 i 阶到第 i+1 阶或 i+2 阶的转移：

若前一步为 j=0（无冷却）：
- 选择爬 1 阶：到达 i+1，花费增加 cost[i+1]，新状态为 dp[i+1][0]。

\[ dp[i+1][0] = \min(dp[i+1][0], dp[i][0] + cost[i+1]) \]

选择爬 2 阶：到达 i+2，花费增加 cost[i+2]，新状态为 dp[i+2][1]（下一步需冷却）。

\[ dp[i+2][1] = \min(dp[i+2][1], dp[i][0] + cost[i+2]) \]

若前一步为 j=1（处于冷却期）：
- 必须跳过当前阶 i，直接到 i+1 阶（爬1阶），且跳过操作不支付花费。到达 i+1 后，冷却结束，状态变为 j=0。

\[ dp[i+1][0] = \min(dp[i+1][0], dp[i][1]) \]

 注意：这里 `i` 是冷却期所在的阶，跳过它后到达 `i+1` 阶，但 `i+1` 阶的花费在爬到时才支付（在其他转移中处理）。

步骤3：初始条件与边界处理

起点为地面（i=-1），花费为0，且未开始爬梯，可视为前一步为 j=0。
初始化一个虚拟点 i=-1，令 dp[-1][0] = 0。
实际编程时，可将 i 平移至从 0 开始，用 dp[0][0] = 0 表示起点。

终点处理：

需越过最后一阶楼梯（索引 n-1），即最终状态应为 i >= n。
当 i = n-1 或 i = n-2 时，若再爬1或2阶可越过终点，此时不再支付花费。

步骤4：具体推导示例
以 cost = [10, 15, 20, 10, 5]（n=5）为例：

起点 i=0（对应地面），dp[0][0] = 0。
从 i=0, j=0 出发：
- 爬1阶到 i=1：花费 +15 → dp[1][0] = 15
- 爬2阶到 i=2：花费 +20 → dp[2][1] = 20
从 i=1, j=0 出发：
- 爬1阶到 i=2：花费 +20 → dp[2][0] = min(∞, 15+20)=35
- 爬2阶到 i=3：花费 +10 → dp[3][1] = 15+10=25
从 i=2, j=1（冷却期）出发：
- 跳过 i=2，直接到 i=3，不支付花费 → dp[3][0] = min(∞, 20)=20
从 i=2, j=0 出发：
- 爬1阶到 i=3：花费 +10 → dp[3][0] = min(20, 35+10)=20
- 爬2阶到 i=4：花费 +5 → dp[4][1] = 35+5=40
从 i=3, j=0 出发：
- 爬1阶到 i=4：花费 +5 → dp[4][0] = 20+5=25
- 爬2阶到终点（i=5）：越过后无花费 → 总花费 = 20
从 i=3, j=1 出发：
- 跳过 i=3，到 i=4 → dp[4][0] = min(25, 25)=25
从 i=4, j=0 出发：
- 爬1阶到终点：花费 0 → 总花费 = 25
- 爬2阶到终点：花费 0 → 总花费 = 25

最终最小花费为 min(20, 25) = 20？但注意路径检查：

路径 0→2（冷却）→3→终点：花费 20+10=30（错误，因冷却期跳过2后到3，需支付3的花费10）。
正确计算：从 i=2, j=1 到 i=3 不支付2的花费，但到3时需支付3的花费（在 i=3, j=0 的转移中支付）。
修正后最小花费为 25（路径：0→1→3→终点：15+10=25）。

步骤5：算法实现与复杂度

使用 dp[i][j] 数组，i 从 0 到 n，j 取 0 或 1。
遍历 i，根据 j 进行状态转移。
最终答案为 min(dp[n][0], dp[n][1], dp[n-1][0], dp[n-1][1])（考虑从不同位置越过终点）。
时间复杂度：O(n)，空间复杂度：O(n)（可优化为O(1)）。

此问题通过状态机模型清晰刻画了带冷却时间的爬楼梯过程，是线性动态规划的典型变种。

线性动态规划：最小花费爬楼梯的变种——带冷却时间的最小花费爬楼梯题目描述假设你正在爬楼梯。楼梯共有 n 阶，每次你可以爬 1 阶或 2 阶，但每次爬完 2 阶后，必须等待一个冷却时间（即下一步不能立即爬，需要跳过一步）。每阶楼梯有一个非负体力花费值 cost[i] （从索引 0 开始），你每爬到一阶楼梯就要支付对应的花费。求从地面（起点，在楼梯底部）爬到楼梯顶部（即越过最后一阶楼梯）的最小总花费。注意：起点和终点均不收取花费。示例输入： cost = [10, 15, 20, 10, 5] 输出： 25 解释：路径为：起点 → 第2阶（花费15）→ 冷却（跳过第3阶）→ 第4阶（花费10）→ 终点。总花费为 15 + 10 = 25。解题过程步骤1：理解问题与状态定义冷却时间规则：若当前爬了 2 阶，下一步必须跳过一阶（即冷却一阶）。目标：最小化总花费，且起点和终点无花费。关键点：需要记录前一步是否爬了 2 阶，以决定当前能否行动。定义状态：设 dp[i][j] 表示到达第 i 阶楼梯时的最小累计花费，其中 j 表示前一步的跳跃类型： j = 0 ：前一步爬了 1 阶（无冷却限制，下一步可爬1或2阶）。 j = 1 ：前一步爬了 2 阶（处于冷却期，下一步只能爬1阶，且跳过当前阶）。注意： i 从 0 开始（第0阶对应第一阶楼梯），终点为 n （即越过第 n-1 阶）。步骤2：状态转移方程考虑从第 i 阶到第 i+1 阶或 i+2 阶的转移：若前一步为 j=0 （无冷却）：选择爬 1 阶：到达 i+1 ，花费增加 cost[i+1] ，新状态为 dp[i+1][0] 。 \[ dp[ i+1][ 0] = \min(dp[ i+1][ 0], dp[ i][ 0] + cost[ i+1 ]) \] 选择爬 2 阶：到达 i+2 ，花费增加 cost[i+2] ，新状态为 dp[i+2][1] （下一步需冷却）。 \[ dp[ i+2][ 1] = \min(dp[ i+2][ 1], dp[ i][ 0] + cost[ i+2 ]) \] 若前一步为 j=1 （处于冷却期）：必须跳过当前阶 i ，直接到 i+1 阶（爬1阶），且跳过操作不支付花费。到达 i+1 后，冷却结束，状态变为 j=0 。 \[ dp[ i+1][ 0] = \min(dp[ i+1][ 0], dp[ i][ 1 ]) \] 注意：这里 i 是冷却期所在的阶，跳过它后到达 i+1 阶，但 i+1 阶的花费在爬到时才支付（在其他转移中处理）。步骤3：初始条件与边界处理起点为地面（ i=-1 ），花费为0，且未开始爬梯，可视为前一步为 j=0 。初始化一个虚拟点 i=-1 ，令 dp[-1][0] = 0 。实际编程时，可将 i 平移至从 0 开始，用 dp[0][0] = 0 表示起点。终点处理：需越过最后一阶楼梯（索引 n-1 ），即最终状态应为 i >= n 。当 i = n-1 或 i = n-2 时，若再爬1或2阶可越过终点，此时不再支付花费。步骤4：具体推导示例以 cost = [10, 15, 20, 10, 5] （n=5）为例：起点 i=0 （对应地面）， dp[0][0] = 0 。从 i=0, j=0 出发：爬1阶到 i=1 ：花费 +15 → dp[1][0] = 15 爬2阶到 i=2 ：花费 +20 → dp[2][1] = 20 从 i=1, j=0 出发：爬1阶到 i=2 ：花费 +20 → dp[2][0] = min(∞, 15+20)=35 爬2阶到 i=3 ：花费 +10 → dp[3][1] = 15+10=25 从 i=2, j=1 （冷却期）出发：跳过 i=2 ，直接到 i=3 ，不支付花费 → dp[3][0] = min(∞, 20)=20 从 i=2, j=0 出发：爬1阶到 i=3 ：花费 +10 → dp[3][0] = min(20, 35+10)=20 爬2阶到 i=4 ：花费 +5 → dp[4][1] = 35+5=40 从 i=3, j=0 出发：爬1阶到 i=4 ：花费 +5 → dp[4][0] = 20+5=25 爬2阶到终点（i=5）：越过后无花费 → 总花费 = 20 从 i=3, j=1 出发：跳过 i=3 ，到 i=4 → dp[4][0] = min(25, 25)=25 从 i=4, j=0 出发：爬1阶到终点：花费 0 → 总花费 = 25 爬2阶到终点：花费 0 → 总花费 = 25 最终最小花费为 min(20, 25) = 20 ？但注意路径检查：路径 0→2（冷却）→3→终点：花费 20+10=30（错误，因冷却期跳过2后到3，需支付3的花费10）。正确计算：从 i=2, j=1 到 i=3 不支付2的花费，但到3时需支付3的花费（在 i=3, j=0 的转移中支付）。修正后最小花费为 25 （路径：0→1→3→终点：15+10=25）。步骤5：算法实现与复杂度使用 dp[i][j] 数组， i 从 0 到 n ， j 取 0 或 1 。遍历 i ，根据 j 进行状态转移。最终答案为 min(dp[n][0], dp[n][1], dp[n-1][0], dp[n-1][1]) （考虑从不同位置越过终点）。时间复杂度：O(n)，空间复杂度：O(n)（可优化为O(1)）。此问题通过状态机模型清晰刻画了带冷却时间的爬楼梯过程，是线性动态规划的典型变种。