【题解】跳格子游戏

跳格子游戏

http://www.nowcoder.com/questionTerminal/2ae1e475df394b9bbb7c6e5bf40be9ec

题目描述

假设你正在玩跳格子(所有格子排成一个纵列)游戏。需要 跳完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;
}
全部评论

相关推荐

挣K存W养DOG:我记得好多人说这个公司就是白嫖方案的,现在有大体方案要让你给他展示实现细节了,也是无敌了
点赞 评论 收藏
分享
野猪不是猪🐗:现在的环境就是这样,供远大于求。 以前卡学历,现在最高学历不够卡了,还要卡第一学历。 还是不够筛,于是还要求得有实习、不能有gap等等... 可能这个岗位总共就一个hc,筛到最后还是有十几个人满足这些要求。他们都非常优秀,各方面都很棒。 那没办法了,看那个顺眼选哪个呗。 很残酷,也很现实
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务