使用最小花费爬楼梯

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]);
};

总结

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