Coding Exercise – Climbing Stairs – Fibonacci Numbers – C++ – Online Judge

Question: You are climbing stairs. It takes n steps to get to the top. Each time, you can take 1 step or 2 steps. How many distinct ways to get to the top?

Problem Description: http://oj.leetcode.com/problems/climbing-stairs/

This problem may look difficult at first, but when you think for a second, you might find it so easy. The answer is Fibonacci Numbers (see here, here)

Well, the original Fibonacci Numbers are defined as sequences:

For this problem, we just have to modify a little bit:

and because for only 1 step, there is only 1 distinct way and for 2 steps, we have two solutions: 1 + 1 or 2.

The rest is as Fibonacci series. The because from the current position, we are possibly from previous two positions, F(n-1) and F(n-2).

You can use recursion, but this can be solved by a more effective iterative solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        // f(n) = f(n - 1) + f(n - 2)
        int a = 1, b = 2, c = a + b;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        // f(n) = f(n - 1) + f(n - 2)
        int a = 1, b = 2, c = a + b;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

Or you prefer a more straightforward recursive function:

1
2
3
4
5
6
7
8

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

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

Note: The recursive will yield TIME LIMIT EXCEEDED on test 44.  That is because, the recursive function usually computes intermediate values many many times. For example, , .  is computed twice. 

–EOF (The Ultimate Computing & Technology Blog) —