在这里，可以思考一下：可以根据第一步的走法把所有走法分为两类：
① 第一类是第一步走了 1 个台阶
② 第二类是第一步走了 2 个台阶
所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 ，然后加上先走 2 阶后，n-2 个台阶的走法。
用公式表示就是：
f(n) = f(n-1)+f(n-2)
有了递推公式，递归代码基本上就完成了一半。那么接下来考虑递归终止条件。
当有一个台阶时，我们不需要再继续递归，就只有一种走法。
所以 f(1)=1。
通过用 n = 2，n = 3 这样比较小的数试验一下后发现这个递归终止条件还不足够。
n = 2 时，f(2) = f(1) + f(0)。如果递归终止条件只有一个f(1) = 1，那 f(2) 就无法求解，递归无法结束。
所以除了 f(1) = 1 这一个递归终止条件外，还要有 f(0) = 1，表示走 0 个台阶有一种走法，从思维上以及动图上来看，这显得的有点不符合逻辑。所以为了便于理解，把 f(2) = 2 作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走。
总结如下：
① 假设只有一个台阶，那么只有一种走法，那就是爬 1 个台阶
② 假设有两个个台阶，那么有两种走法，一步走完或者分两步来走
通过递归条件：
1f(1) = 1;2f(2) = 2;
3f(n) = f(n-1)+f(n-2)
很容易推导出递归代码：
1int f(int n) {2 if (n == 1) return 1;
3 if (n == 2) return 2;
4 return f(n-1) + f(n-2);
5}
通过上述三个示例，总结一下如何写递归代码：
1.找到如何将大问题分解为小问题的规律
2.通过规律写出递推公式
3.通过递归公式的临界点推敲出终止条件
4.将递推公式和终止条件翻译成代码
什么是动态规划介绍动态规划之前先介绍一下分治策略（Divide and Conquer）。
分治策略将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。
因为在求解大问题时，需要递归的求小问题，因此一般用「递归」的方法实现，即自顶向下。
动态规划（Dynamic Programming）动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。
其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。
即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。
与「分治策略」「动态规划」概念接近的还有「贪心算法」「回溯算法」，由于篇幅限制，程序员小吴就不在这进行展开，在后续的文章中将分别详细的介绍「贪心算法」、「回溯算法」、「分治算法」，敬请关注：）
将「动态规划」的概念关键点抽离出来描述就是这样的：
1.动态规划法试图只解决每个子问题一次
2.一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
从递归到动态规划还是以 爬台阶 为例，如果以递归的方式解决的话，那么这种方法的时间复杂度为O(2^n)，具体的计算可以查看笔者之前的文章 《冰与火之歌：时间复杂度与空间复杂度》。
相同颜色代表着 爬台阶问题 在递归计算过程中重复计算的部分。
通过图片可以发现一个现象，我们是 自顶向下 的进行递归运算，比如：f(n) 是f(n-1)与f(n-2)相加，f(n-1) 是f(n-2)与f(n-3)相加。
思考一下：如果反过来，采取自底向上，用迭代的方式进行推导会怎么样了？