n步,采取1、2或3步。有几种方法可以到达顶峰? [英] n steps with 1, 2 or 3 steps taken. How many ways to get to the top?

查看:115
本文介绍了n步,采取1、2或3步。有几种方法可以到达顶峰?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

如果我们有n个台阶,并且一次可以上升1或2个台阶,则台阶数与爬升方式之间存在斐波那契关系。如果且仅当我们不将2 + 1和1 + 2视为不同时。

If we have n steps and we can go up 1 or 2 steps at a time, there is a Fibonacci relation between the number of steps and the ways to climb them. IF and ONLY if we do not count 2+1 and 1+2 as different.

但是,情况不再如此,除了必须添加外,还添加了一个第三个选择,采取3个步骤。我该怎么做?

However, this no longer the case, as well as having to add we add a third option, taking 3 steps. How do I do this?

我有什么:

1 step = 1 way
2 steps = 2 ways: 1+1, 2
3 steps = 4 ways: 1+1+1, 2+1, 1+2, 3

我不知道从哪里可以找到n个楼梯的数量

I have no idea where to go from here to find out the number of ways for n stairs

我通过对前面的所有组合求和得出n = 4的结果为7,n = 5的结果为14,我得到14 + 7 + 4 + 2 + 1。所以n步的方法= n-1种方法+ n-2种方法+ .... 1种方法,假设我保留了所有值。动态编程。
1 2和3步骤将是正确的基本情况吗?

I get 7 for n = 4 and 14 for n= 5 i get 14+7+4+2+1 by doing the sum of all the combinations before it. so ways for n steps = n-1 ways + n-2 ways + .... 1 ways assuming i kept all the values. DYNAMIC programming. 1 2 and 3 steps would be the base-case is that correct?

推荐答案

我会说公式会以以下方式显示:

I would say that the formula will look in the following way:

K(1) = 1
K(2) = 2
k(3) = 4
K(n) = K(n-3) + K(n-2) + K(n - 1)

该公式表示,要到达第n步,我们必须首先达到:

The formula says that in order to reach the n'th step we have to firstly reach:


  • 第n-3个步骤,然后一次执行3个步骤,即K(n-3)

  • 或第n-2个步骤,然后一次执行2个步骤即K(n-2)

  • 或第n-1个步骤,然后立即执行1个步骤,即K(n-1)

K(4)= 7,K(5)= 13等等。

K(4) = 7, K(5) = 13 etc.

您可以使用递归公式或使用动态编程。

You can either utilize the recursive formula or use dynamic programming.

这篇关于n步,采取1、2或3步。有几种方法可以到达顶峰?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆