n步,采取1、2或3步。有几种方法可以到达顶峰? [英] n steps with 1, 2 or 3 steps taken. How many ways to get to the top?
问题描述
如果我们有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屋!