题解 | #最小花费爬楼梯#

第一种方法(仅限于数据量不要太大的情况使用)：递归。你每跳到一个位置 i 上，要判断当前位置是否已经越界了。如果越界，直接返回结果。如果没有越界，那么从当前位置起跳，还要花费当前位置起跳所需要的金额，所以总的金额数要加上当前位置起跳的金额数。然后进行递归，选取从当前位置起跳 1 步还是 2 步中花费最小的金额。(代码看注释的那一部分，主要是数据量太大的时候不行，这种方法)

第二种方法(应该没有问题)：动态规划。定义一个 dp 数组，用于记录跳到每一个位置上，所需要花费的最小金额数，依次遍历 cost 数组，最终得到了 dp 数组。然后从倒数第一个或倒数第二个台阶起跳，看谁的花费少即可。(代码看高亮的那一部分)

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    /**
    public int minCostClimbingStairs (int[] cost) {
        // write code here
        if (1 == cost.length) {
            return cost[0];
        }
        if (2 == cost.length) {
            return cost[0] <= cost[1] ? cost[0] : cost[1];
        }
        return Math.min(process(cost, 0, 0), process(cost, 1, 0));
    }
    */
    /*
    public int process(int[] cost, int index, int num) {
        if (index > cost.length - 1) {
            return num;
        }
        num += cost[index];
        return Math.min(process(cost, index + 1, num), process(cost, index + 2, num));
    }
    */
    public int minCostClimbingStairs (int[] cost) {
        // dp[i] 表示的是跳到 i 位置上所需要花费的最小金额
        int[] dp = new int[cost.length];
        
        // 由于初始状态时，可以从 0 或者 1 位置上起跳，所以跳到这两个位置上所需要花费的最小金额都为 0
        // i 直接从 2 位置开始计算
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        
        // 最后，我们再判断从倒数第一二个台阶起跳，哪个花费的金额最少
        return Math.min(dp[dp.length - 2] + cost[dp.length - 2], dp[dp.length - 1] + cost[dp.length - 1]);
    }
}