使用最小花费爬楼梯

1. 题目描述

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。

• 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。 示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 解释：你将从下标为 0 的台阶开始。

• 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
• 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
• 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
• 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。

2. 分析

如图所示，只有当从第 i 个台阶向上爬的时候才花费对应的费用 cost[i]，站在楼梯上是不需要支付费用的。**注意：**如果 cost 数组长度为 3，那么其楼梯顶部的下标为 3。 *定义数组 dp[i]:到达 i 位置的最小花费；递推公式：到达 i（i>=2)位置的花费由两部分组成 （1）从 i-1 位置爬一节台阶到达； （2）从 i-2 位置爬两阶台阶到达； 得到 dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。 *初始化：由题目说"可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯",知道 dp[0]=0，dp[1]=0。 *从前向后遍历 dp 数组，题目的解即为 dp[n]。

3. 代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <=n; i++) {//从前向后遍历
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);//递推公式
        }
        return dp[n];
    }
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        System.out.print("请输入台阶数：");
        int n = scan.nextInt();
        int[] cost = new int[n];

        System.out.println("请输入每个台阶的费用（空格分隔）：");
        for (int i = 0; i < n; i++) {
            cost[i] = scan.nextInt();
        }
        Solution solution = new Solution();
        System.out.println(solution.minCostClimbingStairs(cost));
    }
}

需要注意的关键问题

1. 问题理解的准确性

• 误区：容易误解为"站在台阶上就要付费"，实际上是在离开台阶时才需要付费
• 正确理解：cost[i] 是从第 i 个台阶向上爬时需要支付的费用
• 影响：这直接影响状态转移方程的设计和最终答案的计算

2. 边界条件处理

• 起始点：可以从索引 0 或 1 开始，这意味着初始状态有两个选择
• 终点定义：楼梯顶部是指超过最后一个台阶的位置，不是最后一个台阶本身
• 特殊情况：当数组长度 ≤ 2 时需要特殊处理

3. 状态转移方程的设计

• 错误设计：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
• 正确设计：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
• 关键区别：费用是在当前台阶支付的，不是在前一个台阶支付的

4. 最终答案的确定

• 常见错误：直接返回 dp[n-1]
• 正确做法：返回 min(dp[n-1], dp[n-2])，因为从倒数第一或第二个台阶都能直接到达顶部

5. 空间优化的陷阱

• 在进行空间优化时，要注意变量更新的顺序
• 必须先保存旧值，再更新新值，避免数据覆盖错误

解决该问题的启发

1. 动态规划的核心思维模式

• 最优子结构：到达第 i 阶的最小花费 = min(到达 i-1 阶的最小花费, 到达 i-2 阶的最小花费) + 当前阶的花费
• 重叠子问题：每个台阶的最优解都依赖于前面台阶的最优解
• 启发：面对最优化问题，先思考是否具有最优子结构性质

2. 问题建模的重要性

• 准确定义状态：dp[i] 必须明确定义为"到达第 i 个台阶的最小花费"
• 清晰的状态转移：基于问题的实际含义推导转移方程，而不是凭直觉
• 启发：在解决 DP 问题时，花时间准确定义状态比急于写代码更重要

3. 边界条件的系统性思考

• 起始边界：考虑所有可能的起始状态
• 结束边界：明确目标状态的定义
• 启发：边界条件往往决定了算法的正确性，需要系统性地分析所有边界情况

4. 空间优化的通用模式

• 观察依赖关系：如果当前状态只依赖于前 k 个状态，就可以用 k 个变量优化空间
• 滚动数组思想：通过变量轮换来避免存储整个 DP 数组
• 启发：在掌握基础 DP 解法后，思考如何优化空间复杂度是提升算法能力的重要步骤

5. 测试用例设计的策略

• 基础用例：验证算法逻辑正确性
• 边界用例：测试数组长度为 1、2 的情况
• 复杂用例：包含大数值、交替模式等
• 启发：好的测试用例能帮助发现算法中的逻辑漏洞

6. 问题变种的思考

• 如果每次可以爬 1、2、3 步怎么办？
• 如果某些台阶不能踩怎么办？
• 如果费用可以为负数怎么办？
• 启发：掌握基础问题后，思考变种能加深对问题本质的理解

7. 实际应用场景的联想

• 路径规划：在网格中寻找最小代价路径
• 资源分配：在约束条件下寻找最优分配方案
• 金融决策：在多个选择中寻找最优投资策略
• 启发：算法问题往往对应着现实世界中的决策优化问题

总结

这个问题虽然看似简单，但包含了动态规划的多个核心要素。通过深入分析这个问题，我们不仅学会了如何解决具体的爬楼梯问题，更重要的是掌握了动态规划问题的一般解决思路：准确定义状态 → 推导状态转移方程 → 处理边界条件 → 考虑空间优化 → 全面测试验证。

这种系统性的思考方法可以应用到更复杂的动态规划问题中，是算法学习中的重要基础。