由一道简单“动态规划”算法题而引发的思考

假如你正在爬楼梯。需要n阶你才能到达楼顶。每次你只可以爬1或2个台阶，你有多少种方法可以爬到楼顶？

由于算法题做的比较少，我大概归纳出一套解题思路（不知道适不适合全部）：

1、写出具体示例

1层 1    一种

2层 1+1 2    二种

3层 111 12 21    三种

4层 1111 121 211 112 22    五种

5层 11111 221 212 122 1112 2111 1211 1121 八种

2、找出数学关系

这道题在1层和2层看不出数学关系，我觉得大部分题也是这样的。观察得出f(n)=f(n-1)+f(n-2)。等做题做多了再总结下常见的数学关系

3、编程序

首先想到递归，由于递归时间复杂度较大，不可取

我们可以利用for循环和数组解决。

细节：别忘了前面的if(n=0)if(n=1)if(n=2)的返回值