Climbing Stairs

Problem: 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?

Thinking: this is a question reforms Fibonacci numbers. The reason is that consider we have n stairs, then there are two subproblems we can accomplish such task. One is take one step on this level, which leaves the rest n-1 stairs, or we can take 2 steps this level, which leaves that rest n-2 stairs.

Then this routine goes on and on until we have one stairs and no stairs, which both have only one way to climb. Therefore it is identical to Fibonacci numbers. For space complexity, use dynamic programming to solve it.


public class Solution {
    public int climbStairs(int n) {
        int i = 1;
        int j = 1;
        
        for (int x = 0; x < n - 1; x++) {
            int temp = i + j;
            i = j;
            j = temp;
        }
        
        return j;
    }
}
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