# 爬楼梯

​ 大一 -> 大二暑期算法作业

​ 本文档中有对动态规划的解读（来自题解）

​ 分站已经上线简约风算法作业集合（也可以选择阅读模式

# 看到题目的想法

​ 这是一道比较经典的题目，之前好像见过类似的题目，所以上手还是有一些思路的。

# 题目描述

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

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

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

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 题目解答

​ （**ps：** 由于做题时采用的是执行代码，并未提交，提交结果均为后来补上，所以时间均为两天前）

# 1. 动态规划

# （1）解题思路

​ 刚开始事项用递归写一下的，后来发现递归会超时，于是选用了动态规划。

​ 这是一道典型的动态规划题，由于每步只能走一或两阶台阶，所以到达这一阶的方法数是 跨一阶到达 + 跨两阶到达。所以走到第一阶有一种方法，走到第二阶有两种方法，从第三阶开始，每一阶的方法数等于前两阶的方法数的代数和（跨一阶到达 + 跨两阶到达）（ps：可以用数组储存，但没必要，因为我们需要的是最终结果。

​ （有斐波那契那味了。

# （2）代码

​ 由于思路比较简单，也是顺利的写出了代码。（配合题目链接食用）

# C++
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1; // 初始化
        for (int i = 1; i <= n; ++i) { // 遍历计算直到算出想要的结果
            p = q; 
            q = r; 
            r = p + q;
        }
        return r; // 返回想要的结果
    }
};

image-20210827092530062.png

# Java
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1; // 初始化
        for (int i = 1; i <= n; ++i) { // 遍历计算直到算出想要的结果
            p = q; 
            q = r; 
            r = p + q;
        }
        return r; // 返回想要的结果
    }
}

image-20210827092554179.png

# C
1
2
3
4
5
6
7
8
9
int climbStairs(int n) {
    int p = 0, q = 0, r = 1; // 初始化
    for (int i = 1; i <= n; ++i) { // 遍历计算直到算出想要的结果
        p = q;
        q = r;
        r = p + q;
    }
    return r; // 返回想要的结果
}

image-20210827092619237.png

# （3）总结

​ 这样直接计算的方法思路很简单，但是问题是计算的结果无法保留，用一次就要重新计算一次，十分的不方便。

# 2. 斐波那契数列

# （1）解题思路

​ 不难看出，此题的数据就是我们熟悉的斐波那契数列，因此我们可以借助斐波那契数列的通项公式来快速算出我们想要的结果（前一种解发是从头计算出来的，台阶数较大时效率低 。

​ 这种方法简单粗暴，就是通项公式不好记。

​ 通项公式的推导过程就不写了，可以去题解里面看一下。+

题目链接（去看官方题解）：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

# （2）代码

# C++
1
2
3
4
5
6
7
8
class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1); // 斐波那契数列通项公式
        return (int)round(fibn / sqrt5); // 返回结果
    }
};

image-20210827092637917.png

# Java
1
2
3
4
5
6
7
public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1); // 斐波那契数列通项公式
        return (int) Math.round(fibn / sqrt5); // 返回结果
    }
}

image-20210827092704192.png

# C
1
2
3
4
5
int climbStairs(int n) {
    double sqrt5 = sqrt(5);
    double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1); // 斐波那契数列通项公式
    return (int) round(fibn / sqrt5); // 返回结果
}

image-20210827092720313.png

# （3）总结

​ 这种解决办法方便快捷，也不会浪费多余的时间空间来计算，比较好用。（缺点就是通项公式并不容易记住）

# 3. 矩阵快速幂（来自题解）

# （1）解题思路 + 代码

​ 说实话，行看到这种方法的时候感觉回到了线性代数的课堂上，又是熟悉的矩阵操作，让人头疼

​ 具体的解题思路和代码就不搬过来了，可以去官方题解下查看。

题目链接（去看官方题解）：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/

# （2）总结

​ 利用矩阵运算解题的方法还是没见过的，对我来说比较新奇，还需要认真的研究研究。

# 题目总结

​ 这道题的难度中规中矩，但也会有很奇妙很方便的解决方案，也让我知道了运用矩阵运算来解题的方法，很棒。

# 拓展（动态规划）（摘自题解）

​ 本部分附带原作者对本题的总结

不少同学对动态规划还处于朦胧状态，我特意录了一期视频，讲一讲动态规划解题方法论，这里详细介绍了动规五部曲，相信结合本篇题解，会对你学习动态规划有所帮助。

视频链接：https://www.bilibili.com/video/BV13Q4y197Wg)

做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目 AC 之后，都不太清楚 dp [i] 表示的是什么。

这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

  1. 确定 dp 数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp 数组如何初始化
  4. 确定遍历顺序
  5. 举例推导 dp 数组

一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？

因为一些情况是递推公式决定了 dp 数组要如何初始化！

后面的讲解中我都是围绕着这五点来进行讲解。

可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题目就解出来了。

其实 确定递推公式 仅仅是解题里的一步而已！

一些同学知道递推公式，但搞不清楚 dp 数组应该如何初始化，或者正确的遍历顺序，以至于记下来公式，但写的程序怎么改都通过不了。

后序的讲解的大家就会慢慢感受到这五步的重要性了。

# 动态规划应该如何 debug

相信动规的题目，很大部分同学都是这样做的。

看一下题解，感觉看懂了，然后照葫芦画瓢，如果能正好画对了，万事大吉，一旦要是没通过，就怎么改都通过不了，对 dp 数组的初始化，递归公式，遍历顺序，处于一种黑盒的理解状态。

写动规题目，代码出问题很正常！

找问题的最好方式就是把 dp 数组打印出来，看看究竟是不是按照自己思路推导的！

一些同学对于 dp 的学习是黑盒的状态，就是不清楚 dp 数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。

这是一个很不好的习惯！

做动规的题目，写代码之前一定要把状态转移在 dp 数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

然后再写代码，如果代码没通过就打印 dp 数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。

这也是我为什么在动规五步曲里强调推导 dp 数组的重要性。

举个例子哈：在「代码随想录」刷题小分队微信群里，一些录友可能代码通过不了，会把代码抛到讨论群里问：我这里代码都已经和题解一模一样了，为什么通过不了呢？

发出这样的问题之前，其实可以自己先思考这三个问题：

  • 这道题目我举例推导状态转移公式了么？
  • 我打印 dp 数组的日志了么？
  • 打印出来了 dp 数组和我想的一样么？

如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历 dp 数组的顺序。

然后在问问题，目的性就很强了，群里的小伙伴也可以快速知道提问者的疑惑了。

注意这里不是说不让大家问问题哈， 而是说问问题之前要有自己的思考，问题要问到点子上！

大家工作之后就会发现，特别是大厂，问问题是一个专业活，是的，问问题也要体现出专业！

如果问同事很不专业的问题，同事们会懒的回答，领导也会认为你缺乏思考能力，这对职场发展是很不利的。

所以大家在刷题的时候，就锻炼自己养成专业提问的好习惯。

# 总结

这一篇是动态规划的整体概述，讲解了什么是动态规划，动态规划的解题步骤，以及如何 debug。

动态规划是一个很大的领域，今天这一篇讲解的内容是整个动态规划系列中都会使用到的一些理论基础。

在后序讲解中针对某一具体问题，还会讲解其对应的理论基础，例如背包问题中的 01 背包，leetcode 上的题目都是 01 背包的应用，而没有纯 01 背包的问题，那么就需要在把对应的理论知识讲解一下。

大家会发现，我讲解的理论基础并不是教科书上各种动态规划的定义，错综复杂的公式。

这里理论基础篇已经是非常偏实用的了，每个知识点都是在解题实战中非常有用的内容，大家要重视起来哈。

# 原作者对本题总结

这道题目和动态规划：斐波那契数题目基本是一样的，但是会发现本题相比动态规划：斐波那契数难多了，为什么呢？

关键是 动态规划：斐波那契数 题目描述就已经把动规五部曲里的递归公式和如何初始化都给出来了，剩下几部曲也自然而然的推出来了。

而本题，就需要逐个分析了，大家现在应该初步感受出关于动态规划，你该了解这些！里给出的动规五部曲了。

简单题是用来掌握方法论的，例如昨天斐波那契的题目够简单了吧，但昨天和今天可以使用一套方法分析出来的，这就是方法论！

所以不要轻视简单题，那种凭感觉就刷过去了，其实和没掌握区别不大，只有掌握方法论并说清一二三，才能触类旁通，举一反三哈！

# 原作者的题目解答

原作者的题目解答：https://leetcode-cn.com/problems/climbing-stairs/solution/dai-ma-sui-xiang-lu-dong-tai-gui-hua-jin-y1hw/