首页 > 试题广场 >

又见台阶

[编程题]又见台阶

热度指数：1322 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

台阶一共有 ${n}$ 层，有一些台阶上有积水。

牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。

已知有 ${m}$ 个台阶上有积水。
请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第 ${n}$ 层，则答案为0。

为了防止答案过大，答案对1e9+7取模。

示例1

输入

9,3,[1,3,5]

输出

说明

因为1，3，5都不能走，所以第一步可以跳到第7层或者第9层
所以一共两种方案：
1. 第一步跳7，第二步跳1，第三步跳1
2. 第一步跳9

备注:



第一个参数代表台阶的阶数
第二个参数m代表有多少层台阶有积水
第三个参数vector a包含m个数字，每个数字代表第层台阶有积水。保证没有重复元素且以升序给出。

算法知识视频讲解

小洋芋热爱NLP

发表于 2021-08-12 00:05:48

- 题目描述：- 题目链接：https://www.nowcoder.com/practice/fac4dc5774204806b7f07ac9e00fb073?tpId=196&&tqId=37241&rp=1&ru=/activity/oj&qru=/ta 展开全文

闲敲棋子~

发表于 2021-04-01 21:14:39

Python版本描述显然，偶数台阶的跳法数等于之前所有奇数台阶的跳法数之和；奇数台阶的跳法数等于之前所有偶数台阶的跳法数之和故： class Solution: def solve(self , n , m , a ): mask = a[::-1] wma 展开全文

xqxls

发表于 2021-08-12 14:03:11

题意整理总共有n层台阶，起初牛牛在第1层。牛牛每次能跳奇数层台阶，问有多少种不同的跳法到达第n层台阶（不能踩到积水的台阶）。方法一（记忆化递归） 1.解题思路递归终止条件：只有0层或1层的时候，共1种方案，返回1。递归如何推进：当前层的方案数，需要借助之前所有相隔奇数层的方案数来计算展开全文

SandMonth

发表于 2021-09-14 17:58:23

又见台阶一共又n层台阶有些台阶上有积水，牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n曾，但他不想在跳跃的过程中跳到有积水的台阶，现在已知有m个台阶上有积水，问牛牛在不跳到积水台阶的情况下跳到第n层有多少种跳法，答案对取模案例输入：9,3,[1,3,5]返回值：2说明：因为1，展开全文

曾经不是人

发表于 2020-07-12 14:20:32

设f[i]表示0跳到i的方法数，显然有若i是积水，f[i]=0; 若i为偶数，则i是由奇数跳转过来，有f[i] = sum(f[k]) (k为小于i的奇数) 若n为奇数，则n是由偶数跳转过来，有f[i] = sum(f[k]) (k为小于i的偶数)由于每次计算都只涉及奇数和与偶数和，那我们完全没展开全文

摸鱼学大师

发表于 2021-08-10 21:08:43

思路：题目的主要信息：跳上n级台阶，每次只能跳奇数级 a数组中存放着不能跳上的台阶序号达不到n级就返回0 求跳上n级的方案数，结果需要取模1e9+7 方法一：动态规划具体做法：我们可以用动态规划，辅助数组dp，其中表示i级台阶方法数，有如下情况：如果i级台阶有积水，如果i为奇数，那它展开全文

球球了给孩子一个offer吧

发表于 2021-08-13 00:06:09

题目：台阶一共有n层，有一些台阶上有积水。牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。已知有m个台阶上有积水。请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第n层，则答案为0。为了防止答案过大，答案对1e9+7取模。方法一展开全文

认认真真coding

发表于 2021-08-15 20:12:58

题目描述台阶一共有n层，有一些台阶上有积水。牛牛一开始在第0层，它每次可以跳奇数层台阶，他想跳到第n层，但是它不希望在跳跃的过程中踩到积水。已知有m个台阶上有积水。请问牛牛在不踩到积水的情况下跳到第n层有多少种不同的方案。如果不可能到达第n层，则答案为0。为了防止答案过大，答案对1e9+7取模展开全文

问题信息

动态规划

难度：

4条回答 10收藏 2957浏览

通过挑战的用户

查看代码

牛客25939...

2022-04-06 21:02:49
祈求顺利毕业

2022-03-06 00:12:11
syfzzz

2021-12-25 19:20:31
煌爸爸

2021-10-26 18:14:50
马叉虫777

2021-10-25 14:01:15

又见台阶

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题