9.2 爬楼梯

70. 爬楼梯

确定dp[i]的含义，爬到第i层楼梯右dp[i]种方法：
第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去。
dp[i] = dp[i-1] + dp[i - 2]

很像斐波那契数列：爬到第 n 级台阶的方法个数等于爬到 n - 1 的方法个数和爬到 n - 2 的方法个数之和。

如何初始化dp数组呢，首先我们要明确的是dp[0]是没有意义的，你爬0层有什么？？
从i = 1和i = 2 初始化

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        //初始化dp数组
        int [] dp = new int [n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]
题目中说了：每当你爬上一个阶梯你都要花费对应的体力值
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];**

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1],dp[i - 2]) + cost[i] ;
        }
        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }
}

参考：https://www.programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html