746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

##题目

题解

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp=new int[cost.length+1];
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<cost.length+1;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
}

此题主要考察动态规划的问题，动态规划主要抓住以下五个点，可以方便自己理清思路：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

注意：dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。
推导递推的方法：可以这样想，当我要到dp[i]时，是不是需要知道dp[i-1]（此前所花费的值）和cost[i-1]（当前要花费的值）的和或者dp[i-2]和cost[i-2]的和，这样就有两种可能，所以需要比较这两种可能。