剑指 Offer 10- II. 青蛙跳台阶问题

碎碎念
解析
如何规划？
代码
杂谈
碎碎话

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

1 2	输入：n = 2 输出：2

示例 2：

1 2	输入：n = 7 输出：21

示例 3：

1 2	输入：n = 0 输出：1

提示：

1	0 <= n <= 100

碎碎念

今天是2022年的5月14日，周六

最近总觉得自己学习的效率不太高，一直在寻找一种比较适合自己的方式。一直以来我都懒于做时间规划，这也导致我做事经常不能够集中。所以也尝试每天列一些Todo清单，完成以后就把它✅掉，于是在做一天事下来后发现，原来自己每天完成的东西还是挺多的。（成就感油然而生！）

倒霉的是可能最近跑步过余猛烈，右脚现在生疼，不便走路。于是约好今天去划船。（好像并没有因果关系，不过来三亚三年，也没有真正玩过这边的水。这座城市承载了我三年记忆，而我却从未感受到它多少的存在，我见的最多的是屏幕上的字符，它的山水烟火，很遗憾没能使我驻足，并不需要依靠什么自制力，单单朴素的钱包就足够抵御这样的吸引… 如今不久就要离开这座城市，而日后朋友们也都相继离开，他们走后，我大抵不会有多大机会再回到这片承载了我三年记忆的城市了。）

所以趁这不太久的时间，尽量体会一下这片风土人情吧。

感慨就说到这里，白天还是继续学习吧，我来聊聊困惑我长久的动态规划。（事实上就在写了这篇文章时，我仍然对着块没有多大的顿悟，仅有一些经验）

解析

这是一道经典的动态规划题目。经典到没有解析。X

首先，如何想到使用动态规划？（当然我在没练动态规划之前肯定是想不到这个的）

动态规划最首要的特征是，当前的状态是可以通过之前的状态推算的，是逐级递推的。所以，如果有题目能够满足这样的条件，那么它大抵是能够使用动态规划的思路去解决。

在这题中，青蛙可以一次可以跳上1级台阶，也可以一次跳上2级台阶。

那么则有：

n	1	2	3	4	5
ans	1	2	3	5	8

看着有点像斐波那契数列对吧，事实上确实是。

那么为什么会这样，我们来捋一捋，看看能不能发现什么规律。

n=1

只需要跳一个台阶。次数为1

总次数为1

n=2

一次跳2个台阶，次数为1
在n为1的基础上再跳1个台阶，n为1的次数为1，所以该次数也为1

所以总次数为2

n=3

在n为1的基础上跳2个台阶，n为1的次数为1，所以该次数也为1
在n为2的基础上跳1个台阶，然而n为2有两种情况，所以该次数为2

所以总次数为3

n=4

由于青蛙一次最多只能跳2个台阶，这意味着n=4时，它的落脚前最近的位置是在n=2，（n=1时青蛙最多只能到达3）这个应该能够理解，未来忘记了思路的自己，再看到这道题，有没有恍然大悟的感觉（我会庆幸此时写下文章的自己）。

在n为2的基础上跳2个台阶，n为2的次数为2，所以该次数也为2
在n为3的基础上跳1个台阶，然而n为3有3种情况，所以该次数为3

所以总次数为5

n=5

n=6

…

如此。是否会有点感觉呢。

注意一点，这种句式可能会使我的解释给人造成误导，即

在n为x的基础上跳x个台阶，n为x的次数为k，所以该次数也为k

你可能会疑惑为什么也是k，而不是k + 1呢，因为我初学动态规划也会有这样的疑问，并且在最近我才想到合理的解释，也许是悟性不够吧。

所以这个疑问的答案是什么呢？

我的回答是，向来如此。是的，它本应该就是这样的。（废话）

因为，当n = 4时，若此时🐸在第2级台阶，它要达到4，那么它必须跳2级，这个数列的可能性在给出n时，就已经确定了。

举例，

先给出n = 2，n = 3的可能性，这里step代表其跳到指定台阶的不同步数方案。

n = 2
step = [[1, 1], [2]]

n = 3
step = [[1, 1, 1], [1, 2], [2, 1]]

那么n = 4则有（用我在上方列举的情况做对比）

n = 4 
step_by_2 = [[1, 1, 2], [2, 2]] # 在 n = 2的基础上有
step_by_3 = [[1, 1, 1, 1], [1, 2, 1], [2, 1, 1]] # 在 n = 3的基础上有
step = [[1, 1, 2], [2, 2], [1, 1, 1, 1], [1, 2, 1], [2, 1, 1]] # 两者合并即所有情况

所以，也就不存在+1一说，因为若要到达n级台阶，那么它本就是这样发展的。若在2级台阶时，step = [1, 1]那么下一步就必然是2，step = [1, 1, 2]，它是一个整体，逻辑上与2级台阶的step = [1, 1]等同，仅仅是step数列长度不一样，这个长度不一样是其台阶级数决定的，仅此而已。若+1，就没有意义了。（如果还是不能理解我说的意思，需要自己去悟了，我无法用更好的语言表达了，为此我深感抱歉）

如何规划？

由上部分的解析我们已经可以知道，当前台阶的步数仅与前两次台阶计数的步数有关。

约定一个长度为n的数组dp，规定dp[i]为青蛙跳到第i级台阶的跳法。由于以上的分析我们不难知道，当前台阶的跳法为前两个的台阶的跳法之和。

即dp[i] = dp[i - 1] + dp[i - 2]，这就是本题动态规划的状态转移方程，没错，就是斐波那契的表达式。

代码

class Solution {
public:
    int numWays(int n) {
        int* dp = new int[n + 1];
        if (n == 0) return 1;
        dp[0] = 1;
        dp[1] = 1;
        int mod = 1000000007; // 题目要求取模，否则n过大则答案会溢出
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod; // 状态转移方程
        }
        return dp[n]; // 递推到n即为答案
    }
};