剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：2
示例 2：
输入：n = 7 输出：21
示例 3：
输入：n = 0 输出：1
提示：
0 <= n <= 100 注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/
打表法：
js
/**
* @param {number} n
* @return {number}
*/
const ans = [
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733,
134903163, 836311896, 971215059, 807526948, 778742000, 586268941, 365010934,
951279875, 316290802, 267570670, 583861472, 851432142, 435293607, 286725742,
722019349, 8745084, 730764433, 739509517, 470273943, 209783453, 680057396,
889840849, 569898238, 459739080, 29637311, 489376391, 519013702, 8390086,
527403788, 535793874, 63197655, 598991529, 662189184, 261180706, 923369890,
184550589, 107920472, 292471061, 400391533, 692862594, 93254120, 786116714,
879370834, 665487541, 544858368, 210345902, 755204270, 965550172, 720754435,
686304600, 407059028, 93363621, 500422649, 593786270, 94208912, 687995182,
782204094,
];
var numWays = function (n) {
return ans[n];
};/**
* @param {number} n
* @return {number}
*/
const ans = [
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733,
134903163, 836311896, 971215059, 807526948, 778742000, 586268941, 365010934,
951279875, 316290802, 267570670, 583861472, 851432142, 435293607, 286725742,
722019349, 8745084, 730764433, 739509517, 470273943, 209783453, 680057396,
889840849, 569898238, 459739080, 29637311, 489376391, 519013702, 8390086,
527403788, 535793874, 63197655, 598991529, 662189184, 261180706, 923369890,
184550589, 107920472, 292471061, 400391533, 692862594, 93254120, 786116714,
879370834, 665487541, 544858368, 210345902, 755204270, 965550172, 720754435,
686304600, 407059028, 93363621, 500422649, 593786270, 94208912, 687995182,
782204094,
];
var numWays = function (n) {
return ans[n];
};动态规划：
js
/**
* @param {number} n
* @return {number}
*/
var numWays = function (n) {
if (n < 2) return 1;
let a = 1;
let b = 1;
let ans = 0;
for (let i = 2; i <= n; i++) {
ans = (a + b) % 1000000007;
a = b;
b = ans;
}
return ans;
};/**
* @param {number} n
* @return {number}
*/
var numWays = function (n) {
if (n < 2) return 1;
let a = 1;
let b = 1;
let ans = 0;
for (let i = 2; i <= n; i++) {
ans = (a + b) % 1000000007;
a = b;
b = ans;
}
return ans;
};