首页 > 试题广场 >

跳格子游戏

[编程题]跳格子游戏
  • 热度指数:8982 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
假设你正在玩跳格子(所有格子排成一个纵列)游戏。需要 跳完n 个格子你才能抵达终点。
每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢?
注意:给定 n 是一个正整数。

输入描述:
格子数n


输出描述:
跳完n个格子到达终点的方法
示例1

输入

2

输出

2
头像 牛客题解官
发表于 2020-06-04 15:52:25
精华题解 题目难度:一星 考察点:动态规划 方法:动态规划 分析: 这个题跟之前的跳台阶是一模一样的:一共有n个台阶,青蛙只能跳1阶或者是2阶,问有多少种跳法? 跳台阶思路如下: 假设青蛙跳n个台阶的跳法为f(n)那么: 如果第一次跳的是1阶,那么剩下的n-1个台阶,跳法 展开全文
头像 王清楚
发表于 2020-04-25 13:16:43
题目描述 假设你正在玩跳格子(所有格子排成一个纵列)游戏。需要 跳完n 个格子你才能抵达终点。每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢?注意:给定 n 是一个正整数。 输入描述 格子数n 输出描述 跳完n个格子到达终点的方法 示例1输入 2 输出 2 到达一个格子 展开全文
头像 cchangcs
发表于 2019-07-24 10:49:22
解题思路: 当前阶梯可以由前一级阶梯跳一级到达,也可由前两级阶梯跳两级到达。 完整代码: n = int(input()) if n <= 2:   print(n) else:   dp = [0 for i in range(n)]   dp[ 展开全文
头像 laglangyue
发表于 2020-06-02 17:08:24
动态规划dp 状态压缩,只保留前两个状态import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); 展开全文