70. Climbing Stairs

You are climbing a stair case. It takesnsteps 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?

Note:Givennwill be a positive integer.

//类似于Fibonacci Series

思路1：经典DP题

    public int climStairs(int n){
        int[] res = new int[n+1];  
        res[0] = 1;  
        res[1] = 1;  
        for (int i = 2; i <= n; i++)  
        {  
            res[i] = res[i-1] + res[i-2];  
        }  
        return res[n]; 
    }
}

思路2：也可以递归

    public int climbStairs(int n) {
         if (n==1) return 1;
         if (n==2) return 2;
         return climbStairs(n-1)+climbStairs(n-2);
    }
}