【LeetCode-简单】746. 使用最小花费爬楼梯（详解）

题目

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-cost-climbing-stairs

 

方法1：动态规划

动态规划 三步走

动态规划，就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤，

1.定义dp数组

我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？

2.找出递推关系式

动态规划类似于高中数学的数学归纳法，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。

3.找出初始值

找出了递推公式，我们还需要初始值，因为递推公式就是靠前面的值推出后面的值，但总得有个头吧，这个头就是初始值。

提示

代码如何排错？将dp数组全部输出看看

对动态规划完全不会的同学可以先去做下面两道动态规划入门题

【LeetCode-简单】509. 斐波那契数（详解）

【LeetCode-简单】70. 爬楼梯（详解）

在这道题也是如此

dp[i]是什么：dp[i]：到达顶层 i ，最小的花费

初始化：两个蓝色为两个起点：dp[0] 和 dp[1] 都是0

10：想要到达顶层“2”，你可以从“0”或者“1”跳过来：dp[0] + cost[0] 或者 dp[1] + cost[1]

15：想要到达顶层“3”，你可从“1”或者“2”跳过来：dp[1] + cost[1] 或者 dp[2] + cost[2]

通项公式：i ：想要到达顶层“i”，你可从“i-2”或者“i-1”跳过来：dp[i - 1] + cost[i - 1] 或者 dp[i - 2] + cost[i - 2]

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

动态规划效果非常好