algorithm - n 步，采取 1、2 或 3 步。有多少种方式可以登顶？

Question

如果我们有 n 级台阶并且我们可以一次上 1 或 2 级台阶，则台阶数和攀登台阶的方式之间存在斐波那契关系。当且仅当我们不认为 2+1 和 1+2 不同。

但是，情况不再如此，我们还必须添加第三个选项，采取 3 个步骤。我该怎么做？

我有什么:

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

我不知道从这里到哪里才能找到 n 阶梯的路数

n = 4 时我得到 7，n= 5 时我得到 14 我通过对之前的所有组合求和得到 14+7+4+2+1。所以 n 步骤的方法 = n-1 种方式 + n-2 种方式 + .... 1 种方式假设我保留了所有值。动态编程。1 第 2 步和第 3 步是基本情况，对吗？

Answer 1

我会说这个公式看起来像下面这样:

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

公式表示，为了达到第 n 步，我们必须首先达到:

• 第 n-3 步，然后一次执行 3 步，即 K(n-3)
• 或第 n-2 步，然后一次执行 2 步，即 K(n-2)
• 或第 n-1 步，然后一次执行 1 步，即 K(n-1)

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

您可以使用递归公式或使用动态规划。