algorithm - n-stair/step爬坡问题: cannot conceptualize why 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 这不是关于实现解决方案的问题，而是关于如何解释/理解答案的问题。

Answer 1

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

您引用的帖子采取了(在我看来是)奇怪的步骤来查看过程的结束。

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

• 我们可以采取 1 步，这给我们留下了要解决的 n-1 问题

或

• 我们可以采取 2 个步骤，这就给我们留下了要解决的 n-2 问题。

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

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