70. 爬楼梯

爱被打了一巴掌 2023-10-16 15:52 56阅读 0赞

#### 70. 爬楼梯 ####

*  题干描述
 *  解题思路
 *   *  1. 确定dp数组以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  拓展
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

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

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

注意：给定 n 是一个正整数。

## 解题思路 ##

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

我们来分析一下，动规五部曲：

定义一个一维数组来记录不同楼层的状态

### 1. 确定dp数组以及下标的含义 ###

dp\[i\]： 爬到第i层楼梯，有dp\[i\]种方法

### 2. 确定递推公式 ###

如何可以推出dp\[i\]呢？

从dp\[i\]的定义可以看出，dp\[i\] 可以有两个方向推出来。

首先是dp\[i - 1\]，上i-1层楼梯，有dp\[i - 1\]种方法，那么再一步跳一个台阶不就是dp\[i\]了么。

还有就是dp\[i - 2\]，上i-2层楼梯，有dp\[i - 2\]种方法，那么再一步跳两个台阶不就是dp\[i\]了么。

那么dp\[i\]就是 dp\[i - 1\]与dp\[i - 2\]之和！

所以**dp\[i\] = dp\[i - 1\] + dp\[i - 2\]** 。

在推导dp\[i\]的时候，一定要时刻想着dp\[i\]的定义，否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性！

### 3. dp数组如何初始化 ###

再回顾一下dp\[i\]的定义：爬到第i层楼梯，有dp\[i\]种方法。

那么i为0，dp\[i\]应该是多少呢，这个可以有很多解释，但基本都是直接奔着答案去解释的。

例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp\[0\] = 1，相当于直接站在楼顶。

但总有点牵强的成分。

那还这么理解呢：我就认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp\[0\]就应该是0。

其实这么争论下去没有意义，大部分解释说dp\[0\]应该为1的理由其实是因为dp\[0\]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp\[0\] = 1。

从dp数组定义的角度上来说，dp\[0\] = 0 也能说得通。

需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。

所以本题其实就**不应该讨论dp\[0\]的初始化**！

我相信dp\[1\] = 1，dp\[2\] = 2，这个初始化大家应该都没有争议的。

所以我的原则是：**不考虑dp\[0\]如何初始化**，只初始化dp\[1\] = 1，dp\[2\] = 2，然后从i = 3开始递推，这样才符合dp\[i\]的定义。

### 4. 确定遍历顺序 ###

从递推公式dp\[i\] = dp\[i - 1\] + dp\[i - 2\];中可以看出，遍历顺序一定是从前向后遍历的。

### 5. 举例推导dp数组 ###

举例当n为5的时候，dp table（dp数组）应该是这样的：  
![在这里插入图片描述][057ae38adf58442cae3d3658e0f27287.png]

## 拓展 ##

这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。

这又有难度了，这其实是一个完全背包问题，但力扣上没有这种题目，所以后续我在讲解背包问题的时候，今天这道题还会从背包问题的角度上来再讲一遍。 如果想提前看一下，可以看这篇:**70.爬楼梯完全背包版本**。

此时我就发现一个绝佳的**大厂面试题**，第一道题就是单纯的爬楼梯，然后看候选人的代码实现，如果把dp\[0\]的定义成1了，就可以发难了，为什么dp\[0\]一定要初始化为1，此时可能候选人就要强行给dp\[0\]应该是1找各种理由。那这就是一个考察点了，对dp\[i\]的定义理解的不深入。

然后可以继续发难，如果一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。这道题目leetcode上并没有原题，绝对是考察候选人算法能力的绝佳好题。

这一连套问下来，候选人算法能力如何，面试官心里就有数了。

**其实大厂面试最喜欢的问题就是这种简单题，然后慢慢变化，在小细节上考察候选人**。

## 代码实现 ##

class Solution {
        
       // 70. 爬楼梯
        public int climbStairs(int n){
        
            if(n < 2) return n;
            int a = 1, b = 2, sum = 0;
            for(int i = 3; i <= n; i++){
        
                sum = a + b; // f(i - 1) + f(i - 2)
                a = b; // 记录f(i - 1), 即下一轮的f(i - 2)
                b = sum; // 记录f(i), 即下一轮的f(i - 1)
            }
            return b;
        }
    }

**参考资料**：[代码随想录-70.爬楼梯][-70.]

[Link 1]: https://leetcode.cn/problems/climbing-stairs/
[057ae38adf58442cae3d3658e0f27287.png]: https://img-blog.csdnimg.cn/057ae38adf58442cae3d3658e0f27287.png
[-70.]: https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE