【题解】跳格子游戏

跳格子游戏

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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 11:00
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司7个岗位
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务