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屋！