NC68 跳台阶

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4 (opens new window)

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解答

下面是过程分析。

已知：

1. 爬到第 1 阶，只可能也只用爬 1 阶就能完成，共 1 种爬法
2. 爬到第 2 阶，可能是从先爬 1 阶到第 1 阶，然后再爬 1 阶到第 2 阶；也可能是直接爬 2 阶到第 2 阶，一共 2 种爬法
3. 爬到第 3 阶，可能直接来自于第 1 阶（一共 2 阶的距离），也可能来自于第 2 阶（一共 1 阶的距离），而如何爬到第 1 阶和第 2 阶？有多少种爬法？则回到了步骤 1 和 2

归纳一下：在第 n 阶时，可能是由从第 n-2 阶爬 2 阶达到，也可能由从第 n-1 阶爬 1 阶达到（n>2）


用 f(n) 记录 爬到第 n 阶时可能有多少种爬法，则：

f(1)=1
f(2)=2
f(n)=f(n−2)+f(n−1),n>2

function jumpFloor(n) {
    if (n == 1 || n == 2) {
        return n;
    }
    return jumpFloor(n - 2) + jumpFloor(n - 1);
}
module.exports = {
    jumpFloor: jumpFloor,
};

参考

• 题解 | #NC68 跳台阶# (opens new window)