题目一： 有一个楼梯，总共有n个台阶。每一次，可以上一个台阶，也可以上两个台阶。问： 爬上这样一个楼梯，一共有多少种不同的方法？ 分析： 当n = 1时 f(1) = 1（0到1） 当n = 2时 f(2) = 2（0到1到2，0到2） 当n = 50 时 f(50) = f(48) + f(49) 因为 走到50，只有下面2种可能。 1、从48到50 2、从49到50. 所以得到状态转移方程：f(n) = f(n-1) + f(n-2) 为了使n = 0 时 也满足状态转移, 我们设置 f(0) = 1 (以python代码为例) 时间复杂度O(n), 空间复杂度O(n)。 空间复杂度可以优化成O(1)，如下：

题目二： 有一个楼梯，总共有n个台阶。每一次，可以上一个台阶，也可以上三个台阶。问： 爬上这样一个楼梯，一共有多少种不同的方法？ 分析： 当n = 1时 f(1) = 1（0到1） 当n = 2时 f(2) = 1（0到2） 当n = 3时 f(3) = 2（0到1到2到3， 0到3） 当n = 4时 f(4) = 3（0到1到2到3到4， 0到1到4， 0到3到4） 当n = 50 时 f(50) = f(47) + f(49) 因为 走到50，只有下面2种可能。 1、从47到50 2、从49到50. 所以得到状态转移方程：f(n) = f(n-1) + f(n-3) 为了使n = 0 时 也满足状态转移, 我们设置 f(0) = 1 (以python代码为例) 时间复杂度O(n), 空间复杂度O(n)。 空间复杂度可以优化成O(1)，如下： 题目三： 有一个楼梯，总共有n个台阶。每一次，可以上一个台阶，可以上二个台阶， 也可以上三个台阶。问：爬上这样一个楼梯，一共有多少种不同的方法？ 分析： 当n = 0时 f(0) = 1 当n = 1时 f(1) = 1 当n = 2时 f(2) = 2 当n = 3时 f(3) = 4 当n = 50 时 f(50) = f(47) + f(48) + f(49) 因为 走到50，只有下面3种可能。 1、从47到50 2、从48到50 3、从49到50. 所以得到状态转移方程：f(n) = f(n-1) + f(n-2) + f(n-3) 时间复杂度O(n), 空间复杂度O(n)。 空间复杂度可以优化成O(1)，如下： 题目四： 有一个楼梯，总共有n个台阶。每次可以走任意台阶。 问：爬上这样一个楼梯，一共有多少种不同的方法？ 分析： 当n = 1 时 f(1) = 1 状态转移方程： f(n) = f(n-1) + f(n-2) + … + f(3) + f(2) + f(1) -------(a) f(n-1) = f(n-2) + … + f(3) + f(2) + f(1) ---------------(b) a-b得: f(n) - f(n-1) = f(n-1) 得到 状态转移方程：f(n) = 2 * f(n-1) 时间复杂度O(n), 空间复杂度O(n)。

继续推导：f(n) = 2 * f(n-1) = 2 * 2 * f(n-2) = 2 * 2 * 2 * f(n-3) = 2^(n-1) * f(1) = 2^(n-1) 时间复杂度O(1), 空间复杂度O(1)。