【解题报告】【lintcode111】Climbing Stairs

题意

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

解答

由于一次只能走一步或者两步，所以我们可以直接获得递归的公式，但是当楼梯太多的时候，递归层次太深，会超时。 我们又想到dp，由于一次走一步或者两步，所以可以从上一个状态或者上两个状态到达当前状态，所以可以得到公式 dp[n] = dp[n-1]+dp[n-2] 因为对于dp[n-1]来说，只能走一步，对于dp[n-2]只能走长度2，所以我们把他们的解的个数加起来，就是我们现在的解数了。

代码

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
     int f1,f2,f3 = 0;
     f1 = 1;
     f2 = 2;
     if(n == 0)return 1;
     if(n == 1)return f1;
     if(n == 2)return f2;
     for(int i = 2;i < n;i++){
         f3 = f1 + f2;
         f1 = f2;
         f2 = f3;
     }
     return f3;
    }
}