前两天做算法题，看到一道有意思的题目，由于看到的时候已经快晚上11点了，而我们学校是晚上11点断电熄灯睡觉。我就记下了题目，然后就躺在床上想这个题该怎么解。
题目长这样：
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法。
最开始的思路是可能跟排列组合有关，想了一会儿，发现思路不对啊。又换换思路，心想，可能跟前一项有关，当我试到n=5的时候，发现规律了！n级阶梯的走法数就等于前两项的走法数的和。跟斐波那契数列的公式有点像。唯一的区别就是最开始的两项的值不一样。
第二天早上第一节正好没课，袖子卷起来，打算把昨天的那道题实现了，总共几行代码，
private long an;
public long climbStairs(int n) {
// write your code here
if(n==0) return 1;
int rst[]={1,2};
if(n<3) return rst[n-1];
n=climbStairs(n-1)+climbStairs(n-2);
return an;
}
点击提交，好家伙，结果网站提示“时间超出了限制”。
原因就是使用了递归，我们都知道递归就是调用自身，既然是调用函数，就会有调用函数的开销，在一个函数调用之前需要做许多工作，比如准备函数内局部变量使用的空间、搞定函数的参数等等，而且使用递归调用有时会产生栈区溢出的异常，就是因为方法调用的深度太深了，存不下了。
怎么办呢？我之前看过《剑指offer》这本书，还被我从图书馆借出来了。它里面就提到过怎么不用递归实现斐波那契数列。思想是通过移动两个“指针”实现从前往后算而不是递归那样从后往前算。我们来看看修改之后的代码：
private long an;
public long climbStairs(int n) {
// write your code here
if(n==0) return 1;
int rst[]={1,2};
if(n<3) return rst[n-1];
long a1=1,a2=2;
for(int i=3;i<=n;i++){
an=a1+a2;
a1=a2;//每次都往后移动这两个“指针”
a2=an;
}
return an;
}
更多文章，欢迎访问个人博客我的博客
