loading...

Learn Dynamic Programming using Fibonacci as an example

rattanakchea profile image Rattanak Chea ・3 min read

To be honest, Dynamic Programming (DP) is a topic that is hard for me to wrap my head around. I think one of the reason is that I was not learning it the right way and understand its concept strong enough to build a mental model of how to solve it properly. Often time, either it takes me a very long time to solve a DP problem and forget about it in the next day, or I just can't.

Learning how to learn is important for me to retain as much as possible. And I think that a fibonacci sequence is a great example of learning DP. I will show you 4 different ways to solve it: Recursive, DP using recursive, DP Bottom Up Approach (optimized runtime), DP Bottom Up Approach (optimized space).

Statement

Find the index value, given a number n in the Fibonacci sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ....

A Fibonacci is a sequence of number where the current number is the result of the sum of the previous two numbers. For example, fib(5) should return 5.

Solutions

1. using Recursion

var fibRecursive = function(n) {
    if (n<=2) return 1;
    return fibRecursive(n-1) + fibRecursive(n-2);
}

This implementation is concise and easy to understand.
We just need have base case when n <=2 and do recursive calls on n-1 & n-2.
The drawback is 1 call becomes 2 calls. 2 calls becomes 4. etc. It is exponential.
Time complexity O(2^n) and space complexity is also O(2^n) for all stack calls.

2. DP = recursion + memoziation

In a nutshell, DP is a efficient way in which we can use memoziation to cache visited data to faster retrieval later on.

var mem = [];
var fibRecursiveMem = function (n) {
    if (mem[n]) return mem[n];
    if (n<=2) mem[n] = 1;
    else {
        mem[n] = fibRecursiveMem(n-1) + fibRecursiveMem(n-2);
    }
    return mem[n];
}

This implementation makes use of mem as an array (or hash) to store value of an already computed num. This will greatly reduce the number of call stack and duplicated computation in the call stack.
For example

fib(4) = fib(3) + fib(2)
fib(2), fib(3) were already saved into mem, so will fib(4)
fib(5) = fib(4) + fib(3)
The previously saved fib(3) and fib(4) will be used to avoid duplicated calculation and call stacks

Time complexity O(N), Space O(N)

3. DP Bottom Up approach (Optimized runtime)

var fibBottomUp = (n) => {
    var mem = [];
    for (var i=0; i <=n; i++) {
        if (i == 0) mem[i] = 0;
        else if (i <=2) mem[i] = 1;
        else {
            mem[i] = mem[i-1] + mem[i-2];
        }
    }
    return mem[n];
}

We can further optimize the runtime by using a bottom up solution with a for or while loop. We still use memoization but we no longer have recursive calls.
Time Complexity O(n), space O(n)

3. DP Bottom Up approach (Optimized space)

var fibBottomUp2 = (n) => {
    var first, second = 0;
    for (var i=1; i <=n; i++) {
        if (i == 1) second = 1
        else {
            var temp = second;
            second = first + second;
            first = temp;    
        }
    }
    return second;
}

As you can see, we only need the last two number to calculate the next Fibonacci sequence. With this logic in mind, we can use two variable to store the last two Fibonacci sequence.
Time O(N), Space O(1)

Leave the comments below for more discussions and useful resources.

Further reading:
Source code:
https://github.com/rattanakchea/coding_interview/blob/master/src/fibonacii.js

This blog post include a test case and run time performance
https://medium.com/developers-writing/fibonacci-sequence-algorithm-in-javascript-b253dc7e320e

Posted on by:

Discussion

pic
Editor guide
 

This is a nice explanation of DP and its application to the Fibonacci numbers specifically, but I really don't like the Fibonacci numbers being used as a way to introduce DP, for a few reasons.

First, because some version of (3) is easy to come up without knowing DP, and isn't really a DP solution.

Second, because DP isn't the fastest way to solve the Fibonacci numbers problem. You can do it in O(log n) time and constant memory through exponentiation-by-squaring of a 2x2 matrix!


I think the best problems that get at the "meat" of dynamic-programming take in arrays and not just numbers. That way, there's never any special formula to guess at, and the way the problem is "recursive" becomes more obvious. Here's a couple:

  • You're playing a game like Candy Land. Each turn, you roll a die and move that number of tiles forward. However, some of the tiles are X'd out, and you're not allowed to move to them. (Instead, you roll again). Given a board as a list of TRUE/FALSE tiles (FALSE meaning you cannot move to it), how many distinct paths are there from the first tile to the last tile?

  • Your favorite ice cream parlor is having a month-long promotion. Each day, they have a different special which costs a different amount. You have a loyalty punch card that after K purchases you get a free ice cream! (But, you can wait to use it for a more expensive ice cream if you want). Given a list of the prices each day and K, what is the least money you can spend to get every special ice cream?

 

This post was meant to be build a foundation for DP concepts. Thus the simpler the example, the easier to understand. I like your two questions a lot and those are practical for technical interview. I will spend time and work on those next.

Do you have a favorite book/resource on learning DP/algorithms? Besides the obvious: Leetcode, Cracking the coding interview.