题目难度：一星
考察点：动态规划

方法：动态规划

  1. 分析：

这个题跟之前的跳台阶是一模一样的：一共有n个台阶，青蛙只能跳1阶或者是2阶，问有多少种跳法？
跳台阶思路如下:
假设青蛙跳n个台阶的跳法为f(n)那么：
如果第一次跳的是1阶，那么剩下的n-1个台阶，跳法是f(n-1)
如果第一次跳的是2阶，那么剩下的n-2个台阶，跳法是f(n-2)
由此可得：f(n) = f(n-1) + f(n-2)
当n=0时，f(0) = 1
当n=1时，f(1) = 1
当n=2时，f(2) = 2
至此，跳台阶问题已经解决。
同样跳格子游戏跟跳台阶问题的状态转移方程也是一样的，甚至初始化都是一样的，所以直接按照跳台阶问题进行解就可以了。

算法实现：
(1). 输入一个整数n；

(2). 初始化dp[0]=dp[1]=1；
(3). 遍历1-n，根据状态转移方程进行计算；
(4). 输出结果dp[n]。

2. 复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

3. 代码： 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int dp[MAXN];
int main() {
    int n; cin>>n;
    dp[0] = 1, dp[1] = 1;
    for(int i=2; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
    cout<<dp[n]<<endl;
    return 0;
}