楼梯问题递归解法疑问：为何递推式为ways(n)=ways(n-1)+ways(n-2)

先明确核心定义 #

首先要搞清楚ways(n)的含义：从楼梯底部（第0级）爬到第n级的所有不同路径的总数。

解答你的疑问 #

疑问1：为什么不是ways(n-1) + ways(1)？ #

你说的“人在第n-1级需要再爬1级到n级”是对的，但这里的逻辑不是拼接路径，而是基于已到达n-1级的所有路径，追加最后一步爬1级。

• ways(n-1)已经统计了所有能到n-1级的路径，每一条这样的路径，只需要在末尾加一步“爬1级”，就对应一条到n级的新路径。这部分的总数量就是ways(n-1)，因为每一条到n-1的路径都能对应唯一一条到n的路径。
• 而ways(1)是从底部到第1级的路径数，和“从n-1到n”的最后一步没有关系，这里不需要把到n-1的路径和到1的路径做拼接，所以完全不需要加ways(1)。

疑问2：为什么不是ways(n-2) + ways(2)？ #

同样，这里统计的是最后一步直接爬2级到达n级的情况：

• ways(n-2)是所有能到n-2级的路径，每一条这样的路径，在末尾加一步“爬2级”，就对应一条到n级的路径，这部分数量就是ways(n-2)。
• 你可能会疑惑“从n-2级分两次爬1级到n级怎么办？”——这种情况已经被包含在ways(n-1)里了：从n-2爬1级到n-1，再爬1级到n，这属于“从n-1级爬1级到n”的情况，已经被ways(n-1)统计过了。我们要统计的是最后一步的不同选择，这两种选择（最后一步爬1级/爬2级）是完全互斥的，不会重复计算，所以直接相加即可。

内容的提问来源于stack exchange，提问作者ABGR