n 阶梯/台阶爬升问题：无法概念化为什么 T(n) = T(n-1) + T(n-2)

Question

我在概念上无法理解众所周知的 n 阶梯爬升问题的解决方案。 n阶梯问题是：

您还有 n 步要爬。您一次只能爬 1 或 2 个台阶。找到到达第 N 步的方法数。

为简单起见，我们只使用 n = 2 的情况。解决方案是T(n) = T(n-1) + T(n-2)，这当然是斐波那契数列。

关于为什么的解释通常是这样的：

You are at the nth step. How did you get there given that you could climb 1 step or 2 at a time? Well, your previous step must be at either step n-1 (took 1 step) or step n-2 (took 2 steps). Now, there are T(n-1) ways to reach the n-1th step, and T(n-2) ways to reach n-2th steps, which means that there are T(n-2) ways to reach n if your last step was at n-2, and T(n-1) ways to reach n if your last step was at n-1. Those are the only two possibilities of how you finally reached n, so the total number of ways to get to nth step is T(n-1) + T(n-2)

我无法概念化以下部分：

there are T(n-1) ways to reach the n-1th step, and T(n-2) ways to reach n-2th steps, which means that there are T(n-2) ways to reach n if your last step was at n-2, and T(n-1) ways to reach n if your last step was at n-1.

这听起来不对。这个解释似乎自相矛盾。

there are T(n-1) ways to reach the n-1th step

和

and T(n-1) ways to reach n if your last step was at n-1

T(n-2)

也是如此

第二点我也很困惑。当我们说解决方案是 T(n-1) + T(n-2) 时，我的大脑大声喊叫‘但是等一下，你在重复计算。 T(n-1) 已经 包括 T(n-2)'.

谁能帮我从概念上理解 T(n) = T(n-1) + T(n-2)

的原因

PS 这不是关于实施解决方案的问题，而是关于如何 explain/understand 答案的问题。

Answer 1

当然，您在 T(n-1) 和 T(n-2) 中计算了一些重复路径。但是，决赛的最后一步就不一样了！所以，这样想。最后一步可能是 1 或 2。现在，从这个分离中，您将有一条不同的路径，您不必担心建模中的任何事情。

Answer 2

the reason why T(n) = T(n-1) + T(n-2)

您引用的 post 采取了（在我看来是）查看过程的 end 的奇怪步骤。

让我们考虑一下当我们处于流程的 开始 时会发生什么，在 n 个阶梯的底部。我们现在可以做什么？

• 我们可以采取 1 步，这让我们需要解决 n-1 问题

或

• 我们可以采取 2 个步骤，剩下 n-2 问题需要解决。

显然，我们要么做一个，要么做另一个。所以解决n问题的方法数恰好是解决n-1问题的方法数加上解决n-2问题的方法数。

或者，T(n) = T(n-1) + T(n-2).