Number of distinct ways to climb a stair case (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?

Thoughts:
This is just Fibonacci numbers. The number of distinct ways for n steps are the sum of distinct ways for n-1 (because we can move 1 step first, then move the rest n - 1 steps) and distinct ways for n - 2 (because we can move 2 steps first, there are two ways to do it: move 1 steps twice and move 2 steps once, the former is a duplicate for the n - 1 case so we should eliminate).

Code (Java):
Recursive version:

public class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1)
            return 1;
        else
	    return climbStairs(n-1) + climbStairs(n-2);
    }
}

Code (Java):
Iterative version:

public class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n == 1)
            return 1;
        int steps_n_2 = 1;
        int steps_n_1 = 1;
        for(int i = 2; i <= n; ++i) {
            int steps_n = steps_n_1 + steps_n_2;
            steps_n_2 = steps_n_1;
            steps_n_1 = steps_n;
        }
        return steps_n_1;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: