河北省住房和城乡建设厅网站,wordpress七牛云使用,卖钢材做哪个宣传网站,五大门户网站题目#xff1a;
链接#xff1a;剑指 Offer 10- II. 青蛙跳台阶问题#xff1b;LeetCode 70. 爬楼梯 难度#xff1a;简单 相关博文#xff1a;剑指 Offer 10- I. 斐波那契数列#xff08;动态规划打表#xff09;
一只青蛙一次可以跳上1级台阶#xff0c;也可以跳上…题目
链接剑指 Offer 10- II. 青蛙跳台阶问题LeetCode 70. 爬楼梯 难度简单 相关博文剑指 Offer 10- I. 斐波那契数列动态规划打表
一只青蛙一次可以跳上1级台阶也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
示例 1 输入n 2 输出2 示例 2 输入n 7 输出21 示例 3 输入n 0 输出1 提示
0 n 100
解题思路
已知一只青蛙一次只能跳1阶或2阶台阶故可知第n阶的青蛙一定是从第n-1阶或第n-2阶跳过来的得动态规划的状态转移方程为F(N) F(N - 1) F(N - 2)正好为斐波那契数列。 注意这里不能用递归的方式写因为有大量的重复计算具体原因分析见上一篇剑指 Offer 10- I. 斐波那契数列动态规划打表。
代码
class Solution {
public:int numWays(int n) {if(n 1) return 1;int a,b,c;b 1;c 1;for(int i 2; i n; i){a b;b c;c (a b) % 1000000007;}return c;}
};时间复杂度O(n)空间复杂度O(1)。
