Dynamic Programming

Today I stumbled across a very interesting article from Gareth Rees, in which he suggests that what we call Dynamic Programming to describe a technique used when writing combinatorial algorithms, should be called the Tabular Method instead.

I read that and started wondering:

What the hell is dynamic programming anyway?!

So, I kept reading and found a very well written explanation in the same article, with great examples! There was only a small problem: the examples were written in Python. I’m not that illiterate in Python, but I still get confused whenever decorators and stuff like that are used. So, as an exercise, I’ve translated” some of the article to javascript. Just enough to get the whole dynamic programming ( Tabular Method? ) idea.

Dynamic Programming / Tabular Method

The example that he uses in the article is that of the Fibonacci sequence:

Fibonnaci Sequence

He states that if we program this algorithm in a naïve way:

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

It is going to run very slowly:

var start, end, i;
var values = [1, 15, 25, 30, 35, 40];
var result = [];
for(i = 0; i < values.length; i ++){
    start = new Date().getTime();
    f(values[i]);
    end = new Date().getTime();
    result.push((end - start)/1000);
}
console.log(result); //in seconds
>>  [0, 0, 0.031, 0.321, 3.579, 39.858]

If we trace the execution of a small input using console.log, we can see what’s happening:

var f = function(n){
    console.log('Call f(' + n + ')');
    if (n <= 1) return n;
    else return f(n-1) + f(n-2);
}
f(4);
>>
Call f(4)
Call f(3)
Call f(2)
Call f(1)
Call f(0)
Call f(1)
Call f(2)
Call f(1)
Call f(0)

Some of the sub-problems are being calculated more than once: f(2) and f(0) is calculated twice, while f(1) is calculated thrice! You can imagine what happens when the n is big. So, if we store the already calculated results in a table, there is no need to calculate and results more than once! Here is a simple implementation:

var f = (function() {
    var table = { 0: 0, 1: 1 };
    var fib = function(n) {
        var value;
        if (n in table) {
            value = table[n];
        } else {
            value = fib(n - 1) + fib(n - 2);
            table[n] = value;
        }
        return value;
    }
    return fib;
})();

Later, I’ve learned that this method is also called memoization. Do you know the difference? Anyway, now you can try f(1000) and it’s way better than the previous way we were doing things.