You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
仔细想想这其实就是一个斐波那契数列，这样一来问题就变成求斐波那契额数列第n个数的值。
一开始用递归发现效率低导致超时，于是用一个数组来存数列，代码如下：
public class Solution { public int climbStairs(int n) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(1); list.add(2); if(n<=2){ return list.get(n-1); } for(int i=2;i<n;i++){ int one = list.get(i-2); int two = list.get(i-1); int sum = one+two; list.add(sum); } return list.get(n-1); } }
另外一种节省空间的方法：
public class Solution { public int climbStairs(int n) { if(n<=3){ return n; } int preOne=1,preTwo=2,sum=0; for(int i=2;i<n;i++){ sum = preOne+preTwo; preOne = preTwo; preTwo = sum; } return sum; } }
原文：http://www.cnblogs.com/mrpod2g/p/4274500.html