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

方法:动态规划

  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;
}