LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的，Level 1 和 Level 2 学习计划是为初级用户和中级用户准备的，题目覆盖了大多数中层公司面试时所必需的数据结构和算法，Level 3 学习计划则是为准备面试顶级公司的用户准备的。来源

第 11 天

746. 使用最小花费爬楼梯

难度：简单

题目

给你一个整数数组 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 。

题解

• 跟爬楼梯一样爬楼梯，我们要上 3 号阶梯，那么如何才能到达 3 号阶梯呢，有两种选择：从 2 号阶梯走 1 步，或者从 1 号阶梯走 2 步

那么问题的关键就在于，在两种选择中：有几种方法可以到达 2 号阶梯，有几种方法可以到达 1 号阶梯，求两种选择之和就是到达 3 号阶梯的方法数即:

//递推公式

dp[i] = dp[i-1] + dp[i-2];

• 最小花费爬楼梯继续假设我们越过 2 号阶梯，什么是越过 2 号阶梯，就是上了 2 号阶梯再付了 2 号阶梯的继续上楼费(加上 cost[2])就是越过 2 号阶梯

//初始条件

dp[0] = cost[0]; 即越过 0 号阶梯所需最低费用

dp[1] = cost[1]; 即越过 1 号阶梯所需最低费用

所以 dp 数组的每个位置记录的是越过当前位置所需最低的费用

那么回到假设，再越过 2 号阶梯之前，也就是加上 cost[2]之前，所需要的费用如何得到？换句话说，我该怎么到达 2 号阶梯，如果知道怎么到达阶梯，确保到达 2 号阶梯花费最小，就是到达 2 号阶梯之前所需的最小费用，即 Math.min(dp[i-1],dp[i-2])，在加上 cost[2]就是越过 2 号阶梯的最小值了

所以，用动态规划解题：

var minCostClimbingStairs = function(cost) {        let len = cost.length;    let arr = [];    arr[0] = cost[0];    arr[1] = cost[1];
    for(let i = 2; i < len; i++) {        arr[i] = Math.min(arr[i-1] , arr[i-2]) + cost[i]    }
    return Math.min(arr[len-1], arr[len-2]);};

总结

动态规划关键要找到一个等式解题~