有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
如果每次走1级，需要走10步，结果可以表示成（1,1,1,1,1,1,1,1,1,1）；
如果每次走2级，需要走5步，结果可以表示成（2,2,2,2,2,）；
思考一下，你还能写出几种……
那么，共有多少种走法呢？
我们可以这样想，假设我们现在还有最后一步要走，可能的情况有哪些？
1.我们站在第9级上，一步1级后到达顶端；
2.我们站在第8级上，一步2级后到达顶端；
所以，最后一步可以走1级或者2级，不外乎两种情况。
再假设，已知从0级到9级的走法有M种，从0级到8级的走法有N种，那么思考一下，从0到10级的走法和M、N有什么关系呢？从0到10级的走法一共是多少种呢？答案是M+N。
也就是说，用F(n)来表示从0级到n级的走法，可得出
F(9)=M；
F(8)=N；
F(10)=M+N；
F(10)=F(9)+F(8);
如果已知从0到9级的走法和从0到8级的走法，问题就有答案了，那从0级到9级的走法有多少种呢？
我们依然这样想，还有一步就到9级，可能的情况有两种，从8到9和从7到9，已知了从0级到8级的走法有N种，如果再知道从0到7的走法有P种，那么从0到9级的走法就是N+P，那么可得出
F(8)=N；
F(7)=P；
F(9)=N+P；
F(9)=F(8)+F(7);
把一个复杂的问题，逐步简化成简单的问题，我们继续推断，当只剩下2级台阶和1级台阶时的走法分别是2和1。不难归纳出：
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2);(n>=3)
这是一个递归，有了公式和递归结束条件，就可以写出程序了。
方法一：递归
public int getResultByRecursion(int n){
if (n <1) {
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
return getResultByRecursion(n-1) + getResultByRecursion(n-2);
}当n=30时的结果：
时间复杂度为2的n次方。
没错，这是一棵二叉树，如图所示，这里同样颜色的表示重复计算的节点，而且多数都不止重复计算了一次。我们可以对此进行优化，使用哈希表存储已经计算的节点，不再重复计算。
方法二：备忘录算法
public int getResultByMap(int n, Map<Integer,Integer> map){
if (n <1) {
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
if(map.containsKey(n)){
return map.get(n);
}else{
int value = getResultByMap(n-1,map) + getResultByMap(n-2,map);
map.put(n,value);
return value;
}
}
当n=30时的结果：
时间复杂度和空间复杂度都为O(n)。其实，我们无非使用了空间换时间，但这里很多节点不用保存，比如说，我们自底向上地来考虑这个问题，n为1和2时是显而易见的，当n=3时，可通过1和2的结果来得出，当n=4时，可通过2和3的结果来得出，我们只需要保存最近的两个结果就可以了。所以，还可以进一步优化。
方法三：动态规划
public int getResultByDP(int n){
if (n <1) {
return 0;
}
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
int a = 1;
int b = 2;
int temp = 0;
for (int i = 3; i < n+1 ; i++) {
temp = a + b;
a = b;
b= temp;
}
return temp;
}时间复杂度为O(n)，空间复杂度为O(l)。
总结：动态规划是一种解决复杂问题的方法，它将大问题分成小问题或者说子问题，这些子问题是独立的，且会有重叠，也就是各子问题包含公共的子子问题，动态规划不会重复地求解公共子问题，而是对每个子问题只求解一次，将结果保存起来，从而避免每次遇到各个子问题时重新计算结果。适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。
如果问题的一个最优解中包含了子问题的最优解，那么该问题具有最优子结构。在上面的问题中，F(10)=F(9)+F(8)，所以F(9)和F(8)是F(10)的最优子结构。用来求解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题，对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。