假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。,

分析，需求比较简单。拿到这个题目的第一想法就是递归，但是这个递推公式是怎么得来的？我居然陷入了逻辑死胡同，花了很长时间才彻底绕出来了。

不多说，先上图：

图片链接：上楼梯（1次上1台或者2台）问题 | ProcessOn免费在线作图,在线流程图,在线思维导图 |

认真的看上图，可以看出：

上到第1台台阶： 一共有1种方法：即： f(1) = 1

上到第2台台阶： 一共有f(2)种方法：即： f(2) = 2。其实这里也是 f(2) = f(1)的方法上网上走一台，在加另外一种方法，直接从地面迈2台台阶，有就是 f(2) = f(1) +1

上到第3台台阶： 1，先上到第1台，用了f(1)种方法，然后直接跨2步到第3台，用了的方法数还是f(1) 2，先上到第2台，用了f(2)种方法，然后直接跨1步到第3台，用了的方法数还是f(2) 因此方法数为： f(3) = f(1) + f(2)

上到第4台台阶： 1，先上到第2台，用了f(2)种方法，然后直接跨2步到第4台，用了的方法数还是f(2) 2，先上到第3台，用了f(3)种方法，然后直接跨1步到第4台，用了的方法数还是f(3) 因此方法数为： f(4) = f(4-2) + f(4-1)上到第5台台阶： 1，先上到第3台，用了f(3)种方法，然后直接跨2步到第5台，用了的方法数还是f(3) 2，先上到第4台，用了f(4)种方法，然后直接跨1步到第5台，用了的方法数还是f(4) 因此方法数为： f(5) = f(5-2) + f(5-1)

上到第n台台阶： 1，先上到第n-2台，用了f(n-2)种方法，然后直接跨2步到第n台，用了的方法数还是f(n-2) 2，先上到第n-1台，用了f(n-1)种方法，然后直接跨1步到第n台，用了的方法数还是f(n-1) 因此方法数为： f(n) = f(n-2) + f(n-1)

因此，递推公式是： f(n) = f(n-2) + f(n-1)

我一开始的时候理解成了：

从第 n - 2台台阶上去的时候，还要迈一次（2台），从n-1上到n的时候，还要迈一次（1台），因此错误的认为，总方法数是 f(n) = [f(n-2) +2 ]+  [f(n-1) + 1]，将方法和迈的步数搞混了。

从f(n-2)台阶迈到n台台阶（这里只能一次迈2台，否则会重复为f(n-1) ），走到f(n-2)的每一种方法再都迈一次2台台阶到达n台台阶，此时用的方法数还是f(n-2)种。同理，走到f(n-1)的每一种方法再都迈一次1台台阶到达n台台阶，此时用的方法数还是f(n-1)种。走到第n台台阶，只可能从n-2台上来，或者从n-1上来。所以，正确的递推公式是：  f(n) = f(n-2) + f(n-1)

有了递推公式代码就好写了：

有了递推公式，状态转移方程也就很容易写了：

dp[n] =  dp[n-2] + dp[n-1]; dp[0] = 0|1; dp[1] = 1; dp[2] = 2;