algorithm - n 楼梯/台阶攀爬问题 : 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) .