轮滑障碍赛中，共8个障碍物，选手需绕过障碍物滑行抵达终点。若_

cinnnnx

求答疑，为什么两个障碍物的时候有两种滑法。。不是障碍物的右侧出发吗

发表于 2019-09-09 09:23:54 回复(1)

臭布矶

经分析，有1,2,3,4,5,...个障碍物的时候，分别有1,2,3,5,8,...种滑法。

斐波那契数列，f(n)=f(n-1)+f(n-2)，f(8)=34

发表于 2015-09-06 14:19:18 回复(3)

Badrain

发现所有答案都只着重给出了结果，我还是浅显易懂地说一下核心思想吧。

其实这是一道数据结构算法题，可以类比爬楼梯问题，有两种通用的解法：

<1> 递归解法

从终点开始反向考虑：不断重复对每一种状态都考虑滑1个障碍物和滑2个障碍物两种滑行方法......直到最后剩1个障碍物时只有一种滑法，剩2个障碍物时有2种滑法。

图解如下：

最后相加。可以看成算式：

f(5) = f(4) + f(3)

= f(3) + f(2) + f(2) + f(1)

= f(2) + f(1) + f(2) + f(2) + f(1)

= 2 + 1 + 2 + 2 + 1

= 8

<2> 动态规划

从起点开始正向考虑：每次往前推进一个障碍物，考虑到当前障碍物共有多少种滑行方法。（初始情况：到第一个障碍物有一种，到第二个障碍物有两种）。

到当前障碍物有“滑一个障碍物”和“滑两个障碍物”两种滑法：

即用算式表示：

f(1) = 1, f(2) = 2

f(3) = f(2) + f(1) = 3

f(4) = f(3) + f(2) = 5

f(5) = f(4) + f(3) = 8

发表于 2016-08-06 12:12:03 回复(3)

Evan0.0

按照绕过两个障碍物的次数分类：0次有1种情况；1次有7种情况；2次有6*5/2=15种情况；3次有5*4/2=10种情况；4次有1种情况。所以总共的滑法为1+7+15+10+1=34种。

发表于 2015-09-05 23:54:35 回复(1)

狼族099

斐波那契数列，和跳台阶一样

发表于 2015-09-06 14:48:08 回复(0)

张佃鹏

斐波那契数列：

f(n)=f(n-1)+f(n-2) f(1)=1 f(2)=2

这个数字f（8）=34经常出现，大家可以记一下

发表于 2015-10-06 10:12:46 回复(1)

WolffyChen

斐波那契数列：1 2 3 5 8 13 21 34

发表于 2015-09-05 23:07:37 回复(0)

夏日星2016

1+C¹ ₇ +C² ₆ +C³ ₅ +C⁴ ₄

发表于 2015-09-21 23:40:41 回复(1)

华谨舞

斐波那契数列 1 2 3 5 8 13 21 34(滑法)

1 2 3 4 5 6 7 8(障碍物个数)

发表于 2018-10-24 20:24:04 回复(0)

wanye_z

这道题实际上和剑指offer上的青蛙跳是类似的，青蛙跳到n级的台阶上，一次可以跳一级，或者两级，问共有多少种方法？

实际上我们直接就可以推到出来f(n) = f(n - 1) + f(n - 2)，因为跳到n级只能是从n - 1级跳上来或者是n-2级跳上来，所以跳到n - 1级的方法是f(n - 1)，到n - 2级的方法种类数有f(n - 2)，得知。

发表于 2017-09-09 10:56:56 回复(0)

放作夥

从右侧出发让人有联想，以为左右测也是不同决策方法

发表于 2015-12-15 07:08:57 回复(1)

牛客637928519号

排列组合方法： 8个1：1种 1个2和6个1：7种 2个2和4个1：10种(C(5,2))+5种（2个2在一起）=15种 3个2和2个1：6种(C(4,2))+4种（2个1在一起）=10种 4个2：1种

发表于 2022-07-06 18:20:42 回复(0)

牛客756893303号

可以很容易得出，f（1）=1，f（2）=2，f（4）=5，f（5）=8 f（n）=f（n-1）+f（n-2）所以f（8）=f（7）+f（6） =f（6）+f（5）+f（5）+f（4） =f（5）+f（4）+f（5）+f（5）+f（4） =8+5+8+8+5=34

发表于 2022-03-18 17:16:52 回复(0)

Cambell

8个1：1种

1个2和6个1：7种

2个2和4个1：10种(C(5,2))+5种（2个2在一起）=15种

3个2和2个1：6种(C(4,2))+4种（2个1在一起）=10种

4个2：1种

发表于 2019-04-09 15:45:54 回复(0)

yeungkacent

发表于 2016-09-25 10:25:21 回复(0)

二货磁铁

斐波那契数列

这种类型的题目还有青蛙跳，上台阶之类的

发表于 2015-09-07 02:59:46 回复(0)

小太阳201804150935410

这不动态规划吗

发表于 2022-11-30 15:39:24 回复(0)

大好人20190404233700

力扣跳台阶问题，用dp解

发表于 2022-10-14 16:43:45 回复(0)

KKKKK222

f(8)=f(7)+f(6)

f(7)=f(6)+f(5)

f(6)=f(5)+f(4)

……

f(1)=1,f(2)=2

发表于 2020-05-14 10:17:41 回复(0)

MatchOfLin

斐波那契数列

发表于 2019-10-29 15:14:56 回复(0)

轮滑障碍赛中，共8个障碍物，选手需绕过障碍物滑行抵达终点。若

问题信息

热门推荐

相关试题