LeetCode: Climbing Stairs

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?

---

This is a easy DP problem. The formula is sol[n] = sol[n-1] + sol[n-2]. For the nth stair, we can get there from (n-1)th stair or from (n-2)th stair.

C++ Code:

/* func: climb_stair
 * goal: to find out how many ways we can use to climb to the top
 * @param n: number of stairs
 * return: number of ways
 */
/*
 * classical DP problem: sol[n] = sol[n-1] + sol[n-2]
 * complexity: time O(n), space O(n)
 */
int climb_stair(int n){
    if(n <= 1){
        return 1;
    }else if( n == 2){
        return 2;
    }else{
        int *sol = new int[n];
        sol[0] = 1;
        sol[1] = 2;
        for(int i = 2; i < n; ++i){
            sol[i] = sol[i-1] + sol[i-2];
        }
        int result = sol[n-1];
        delete [] sol;
        return result;
    }
}

Python Code:

# func: find the total number of distinct ways to get to the top
# @param n: number of stairs
# @return: total number of ways
def climb_stair(n):
    if n <= 1:
        return 1
    elif n == 2:
        return 2
    else:
        solution = [1,2]
        for _ in xrange(2, n):
            solution.append(solution[-1] + solution[-2])

        return solution[-1]