爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
js
var climbStairs = function (n) {
let dp = [1, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
使用最小花费爬楼梯
leetcode: 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
js
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
输入：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 。
思路
第 i 个台阶可以由第 i 个台阶 或者 第 i -1 个台阶 到达。
要到达 第 i 个台阶，则取决于前面两次 dp 结果：dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
最终比较 i i-1 即可。
js
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
// dp[i] = Math.min()
let len = cost.length;
let dp = [cost[0], cost[1]];
for (let i = 2; i < len; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
//已经在楼顶了，在前两步中找花费最少的
return Math.min(dp[len - 1], dp[len - 2]);
};
优化空间复杂度：
js
/**
* @param {number[]} cost
* @return {number}
*/
var minCostClimbingStairs = function (cost) {
let dp = [cost[0], cost[1]];
for (let i = 2; i < cost.length; i++) {
let dpi = Math.min(dp[0], dp[1]) + cost[i];
dp[0] = dp[1];
dp[1] = dpi;
}
//已经在楼顶了，在前两步中找花费最少的
return Math.min(dp[0], dp[1]);
};