爬楼梯问题

1. 爬楼梯问题

问题: (https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/)

假设你正在爬楼梯，需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢？

分析：

动态规划，将当前问题分解为包含最优子结构的子问题，使用子问题的最优解来解决当前问题。

假设到第n阶的方法有dp[n]种，

那么从前一阶到第n阶有两种方式：

1. 跨1个台阶到达第n阶
2. 跨2个台阶到达第n阶

那么到达第n阶的方法应该是两者之和：dp[n] = dp[n-1] + d[n-2]，就是斐波那契数列

实现：

function climbStairs(n){
    if(n == 1) return 1;
    let pre = 1, 
        cur = 2;
    for(let i=3;i<=n;i++){
        let next = cur + pre;
        pre = cur;
        cur = next;
    }
    return cur;
}

复杂度分析

时间复杂度：O(n)，单循环到 n。
空间复杂度：O(1)，使用常量级空间。

使用斐波那契数列的计算公式，可以将时间复杂度优化到O(logn);

2. 最小消耗爬楼梯

问题：(https://leetcode-cn.com/problems/min-cost-climbing-stairs/)

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例1

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

示例2

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

注意：
cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

分析：

同样是动态规划，假设爬到第n阶的最小消耗为dp[n]，由于上第n阶消耗cost[n]

那么前一阶梯的消耗应该是 dp[n-pre] = dp[n] - cost[n]

一次能爬1至2阶，n-pre只能是n - 1 或 n - 2，取最小的那个，就是最小消耗

dp[n] = min(dp[n - 1],dp[n - 2]) + cost[n]

实现：

function minClimbCost(costs){
    let pre = 0,
        cur = 0;
    for(let i=0;i<costs.length;i++){
        let temp = cur;
        cur = Math.min(pre,cur) + costs[i];
        pre = temp;
    }
    return Math.min(pre, cur);
}

复杂度分析

时间复杂度：O(n)，单循环到 n。
空间复杂度：O(1)，使用常量级空间。