【题解】跳格子游戏

题目描述

假设你正在玩跳格子（所有格子排成一个纵列）游戏。需要 跳完n 个格子你才能抵达终点。
每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢？
注意：给定 n 是一个正整数。

输入描述

格子数n

输出描述

跳完n个格子到达终点的方法

示例1
输入

2

输出

2

到达一个格子的方法有两种，一种是一个格子前，另一种是两个格子前，所以可以建立状态转移方程
,,即可得到结果

#include<iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int dp[1000];
    dp[1]=1;dp[2]=2;
    for(int i = 3 ; i <= n; i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    cout<<dp[n]<<endl;
    return 0;
}

也可以不用开辟数组来存放，因为只有邻近的两个状态是有效的，所以只需要递推一遍就好，

#include<iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans = 1;//表示当前格子的答案
    int a,b;//表示2个格子前，b表示一个格子前
    a = 1;b = 1;
    for(int i = 2 ; i <= n ; i++)
    {
        int temp = ans;
        ans = a+b;
        a = b;
        b = ans;
    }
    cout<<ans<<endl;
    return 0;
}