If you can go up N stairs two steps at a time or one step at a time, how many different ways can you climb the stairs?

This is the fibonacci sequence disguised as the N stairs question.

O(2^n) Solution

Given we have N steps, lets look at our base case.

• If N == 0, then there are 0 ways to climb the stairs.
• If N == 1, then there is 1 way to climb the stairs.
• if N == 2, there are 2 ways to climb the stairs { 1, 1 } { 2 }
• If N == 3, there are 3 ways to climb the stairs { 1, 1, 1 } { 1, 2 } { 2, 1 }
• If N == 4, there are 5 ways to climb the stairs { 1, 1, 1, 1 } { 1, 1, 2 } { 1, 2, 1 } { 2, 1, 1} { 2, 2 }

The sequence here then makes { 0, 1, 2, 3, 5 }

Here we can obviously see that this is related the fibonacci sequence. {0, 1, 1, 2, 3, 5, 8 }

Obviously, the values are very similar, but the value is one before rather than the correct correspondence. We can easily fix this by adding 1 to the value of n before computing it. Then we will always have the next fibonacci calculation.

int fib(int n) {
    if (n == 1 || n == 0)
        return n;
    return fib(n - 1) + fib(n - 2);
}

int countSteps(int steps) {
    if(steps == 0)
        return 0;
    return fib(steps + 1);
}

O(N) Time Solution, O(N) Space - Dynamic Programming

The dynamic programming method involves saving an iteration we've seen before. Note that this is for fibonacci sequence and not N stairs. Your solution can be modified according to the problem.

Here in the above tree, we can obviously many repeated processes. This is very useful and quite unnecessary. If we precompute these values, we can just use the values stored at these nodes rather than branching. This is known as branch pruning.

int fib(int n) {
    int fibArr[n + 1];
    // calculate fib0, fib1 and fib2 as base cases
    fib[0] = 0;
    fib[1] = 1;

    for(int i = 2; i <= n; i++) {
        fibArr[i] = fib[i - 1] + fib[i - 2];    
    }
    return fib[n];
}

O(N) Time Solution O(1) Space - Dynamic Programming

When we're building up and taking a top down approach, we realize that we actually don't have to save any of the previous values as we build up. We really only have to save the values at every iteration since we only need the n - 1 solution and n - 2 solution.

int fib(int n) {
    if(n <= 1) 
        return n;
    int n1 = 0;
    int n2 = 1;
    int fibVal;  

    for(int i = 2; i <= n; i++) {
        fibVal = n1 + n2;
        n2 = n1;
        n1 = fibVal;
    }
}