LintCode-爬楼梯

题目描述：

　　假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

　　比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法

　　返回 3

这是一维数组的动态规划问题，因为一步能爬一步或者两步，step[i] = step[i-1] + step[i-2]

java代码如下：

 1 public class Solution {
 2     /**
 3      * @param n: An integer
 4      * @return: An integer
 5      */
 6     public int climbStairs(int n) {
 7         if(n == 0){
 8             return 1;
 9         }
10         
11         int[] step = new int[n+1];   //因为step[i]代表台阶数为n时的方法数，这里数组长度为n+1
12         step[0] = 1;
13         step[1] = 1;
14         
15         for(int i=2;i<=n;i++){
16             step[i] = step[i-2] + step[i-1];
17         }
18         
19         return step[n];
20     }
21 }

这其实就是斐波那契数