剑指 Offer 10- II. 青蛙跳台阶问题（LeetCode 70. 爬楼梯）（动态规划打表）

题目：

链接：剑指 Offer 10- II. 青蛙跳台阶问题；LeetCode 70. 爬楼梯
难度：简单
相关博文：剑指 Offer 10- I. 斐波那契数列（动态规划打表）

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：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)。