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:

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.