一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入:n = 2
输出:2
示例 2:
输入:n = 7
输出:21
提示:
0 <= n <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
// 当在第n个台阶时 青蛙可能是从n-1处跳的 也有可能是n-2出跳的 // dp[i] 存储在第i个台阶时 跳法的总数 // dp[0]=1 dp[1]=1 dp[2]=dp[0]+dp[1] 与菲波那切数列的区别在于dp[0]!=0 class Solution { public: int numWays(int n) { if(!n) return 1; vector<int> dp(n+1,0); dp[0]=dp[1]=1; for(int cur=2;cur<=n;cur++)dp[cur]=(dp[cur-1]+dp[cur-2])%1000000007; return dp[n]; } };