Leetcode #70 Climbing Stairs

public int climbStairs(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        int a = 1;
        int b = 2;
        int sum = 0;
        for(int i=2;i<n;i++){
            sum = a+b;
            a = b;
            b = sum;
        }
        return sum;
    }

根据题目意思可以得到，每一阶都有1或者2两种走法，那么例如n=5的时候，最后一步可以从第4阶走一步上去，或者从第3阶走两步上去，然后再分析子问题易得f(n=5)即为f(n=4)+f(n=3)，不用担心这两个子问题会有解法重复的问题，因为他们最后一步肯定是不同的。
到此可以简化问题成一个斐波那契数组，但是直接用递归的方法求解时会有超时的问题，所以采用如上的方法求解递归。