题目
- 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模
1e9+7
(1000000007),如计算初始结果为:1000000008,请返回 1。
示例
- 示例1
输入:n = 2
输出:2
- 示例2
输入:n = 7
输出:21
- 示例3
输入:n = 0
输出:1
代码
- 迭代
public int numWays(int n) {
int a = 1, b = 1, sum = 0;
for (int i = 1; i < n; i++) {
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return b;
}
代码分析
:本题与斐波那契数列异曲同工。
- 第0级:一种方式,就是原地不动;
- 第1级:1种方式,即从0走一步到第1级;
- 第2级:2种方式,即从0到1到2,或者直接从0到2;
- 第3级:考虑每次只能上1或者2级,那么到第三级只有两种情况:从第1级上两步到第3级,或者从第2级走一步到第三级。
- ... ...
- 第n级:同上,到第n级只有两种方式:从n-2级走两步到第n级,或者从n-1级走一步到第n级。
- 假设到第n-2级的方式有 f(n-2)种,到第n-1级的方式有f(n-1)种,则到第n级的方式有:f(n-2)1+f(n-1)1=f(n-2)+f(n-1)。
- dp
class Solution {
public:
int numWays(int n) {
if(n <= 1) return 1;
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
//dp[2] = 2;
for(int i = 2; i < n+1; i++){
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}
return dp[n];
}
};