# random thoughts

Go back to the index.

# Dynamic Programming for the Impatient, Dumb and Lazy Ones

By Antoine Grondin, Tuesday November 12, 2013 - Is there an error in this post? Submit a fix here.

Preambule: the algorithms in this page are all implemented in Javascript, and your browser is currently using them to generate the numbers you’ll see below. Please note that I’m not a good Javascript dev and the code I’ve written is hackish at best.

## You Love Recursion

Hello Jim, I’ve been told that you quite enjoy recursion.

You’ve got this nice recursive function that you love and cherish, but oh boy it’s an incredibly prohibitive one to compute! How can you keep the little recursive thing and make it much faster?

You’ve been told that dynamic programming is the Graal. You’ve been told that dynamic programming hard.

However, let me tell you that with enough lazyness, you too can do it while not changing much to your lovely recuring thing.

## The Mighty Change Giving Algorithm

Your professor Ms. Computer Science gave you a cute little thing. It’s not really important to know what this is supposed to do, but she said it computes the change needed to form an amount $n$ with $10$, $5$ and $1$ cents coins (we trust her with that):

function getChange(n) {
recursiveChange(n, 3) // base case is k=3
}

// helper
function recursiveChange (n, k) {

if (k == 1) return 1;

var big = 0;
if (k == 3) { big = 10; }
else        { big = 5;  }

if (n < big) {
return recursiveChange(n, k-1);
}

return recursiveChange(n - big, k) + recursiveChange(n, k-1);
}


Whether the algorithm actually does compute the proper change (or not!) is quite irrelevant to our problem. We just want to make this thing FASTER! Fast like a Rockomax “Mainsail” rocket engine!

Wow, that’s pretty fast! How are we going to do this, Antoine?

Oh well, I’m not too intelligent, but I have a trick! It’s called lazy loading and I’ve heard it’s quite the cool and hip thing. But first, let’s look at how this thing grows!

Well, from the look of it, I’d say this is growing pretty FAST! But that’s not the ‘fast’ we’re looking for. We want this Recursions done column to be little, so that the algorithm itself is FAST!

Note : All along the post, I’ve assumed that faster means less recursions. Let’s just assume that this is true in this algorithm, shall we?

You might have seen the lazy loading pattern in other shapes. It’s quite used in Java (and everything else!) to avoid loading expensive objects until they’re very needed. Here’s an example (the only part of this post that’s written) in Java:

// hugeString is huge, so don't store it by default.
private String hugeString = null;

// People ask for the huge string using this method, always
public String getHugeString() {

// If nobody ever asked for hugeString, it's null so we get it
if (hugeString == null) {
hugeString = Database.getHugeString();
// from now on, hugeString is set
}

// In any case, we return hugeString, whether it was already there or not
return hugeString;
}


That’s pretty simple, right? Let’s see how this applies to our $getChange$ algorithm.

## Identifying Key Informations

There are a few things you need to just know about dynamic programming. Here they are:

### 1. Thou shall need a multi-dimensional array.

$$dynamic\ programming \to array$$

The answer to question 1 is pretty easy: need I use an array? Yes!

### 2. Thou shall know how many dimensions thy array will have, somehow.

$$array[i][j][k]…[x]$$

Let’s look at question 2. To do that, recall the first part of the algorithm:

function recursiveChange (n, k) {
...
}


You can see here that function recursiveChange takes two arguments, n and k. So the answer to question 2 is a 2-dimensional array. That’s pretty easy so far.

### 3. Thou shall know what size thy dimensions will be, somehow.

\begin{align} i&=something\\ j&=somethingElse\\ &\cdots \\ x&=somethingAtLast \end{align}

Now, the harder part; question 3. We need to know how big each argument will be, because that’s how big we need to make the dimensions. So we just look at the code and figure it out with our dumb little brains:

First let’s look at the easy one.

#### How big will k be?

We see in the getChange function that k starts with value $3$.

function getChange(n) {
recursiveChange(n, 3) // base case is k=3
}


Now we look if anything in the helper function recursiveChange will ever make k bigger:

function recursiveChange (n, k) {

if (k == 1) return 1;

var big = 0;
if (k == 3) { big = 10; }
else        { big = 5;  }

if (n < big) {
return recursiveChange(n, k-1);
}

return recursiveChange(n - big, k) + recursiveChange(n, k-1);
}


Nope, never. So $k\leq3$ in any case.

#### How big will n be?

We know that the algorithm starts with initial value n, then recurses with equal or smaller values than n. So n will be as big as n is. This sounds weird, but what it means is that the array will be dynamically sized by a constant 3 and a varying n.

### Putting it 1, 2 and 3 together.

So we need a 2-dimensional array of size $n \times 3$. Let’s call this array memo, short for memoization; a fancy term intelligent people use to show that they have a fancy vocabulary. I use it too, just to feel smart and distingué. You should do that too from now on.

memo = new Array(n);
for (var i = 0; i < memo.length; i++) {
memo = new Array(3);
}


Note: actually, it’s n + 1 and 3 + 1 because prof Ms. Computer Science likes her algorithms 1-indexed.

You can clearly see that the space complexity of your yet-to-be-born algorithm will somehow be bounded below by n. Actually, at least $3n$. The fancy people say $\Omega(n)$.

## Cool Bro, But Where’s My Rockomax-Fast Algorithm?

Well from now on ‘bro’, it will be even easier. Apply the following recipe:

• At the beginning of recursiveChange, look into memo if you don’t know the answer already. If not, change nothing.
if (memo[n][k]) { // we cheat; javascript considers null to be false.
return memo[n][k];
}

• For every recursive call to recursiveChange(i, j), check if memo[i][j] is known.
• If yes, return that value instead of doing the recursion.
• If no, do the recursive call, but save the value you get back into memo[i][j].
if ( !memo[i][j] ) {
memo[i][j] = recursiveChange(i, j);
}
// use memo[i][j]

• When you’re about to return the computed value at the very end, save it into memo first.
memo[i][j] = answer;


## The Quasi End Result

We do as I’ve said above, and replace all the access to lazy ones, and save whatever we compute at each step. Here’s the result:

function getChangeDynamic(n) {
var k = 3;
// create our memo array
var memo = new Array(n);
for (var i = 0; i < memo.length; i++) {
memo[i] = new Array(k);
}
// call the recursive function as usual
recursiveChange(n, k, memo)
}

// a helper to clean up the code a bit
function lazyGet(i, j, memo) {
if ( !memo[i][j] ) {
memo[i][j] = recursiveChange(i, j, memo);
}
return memo[i][j];
}

// Keep the recursive function as is, minus the use of the memoization
function recursiveChange (n, k, memo) {

if (k === 1) {
return 1;
}

// if we know the answer, don't compute anything
if ( memo[n][k] ) {
return memo[n][k];
}

var big = 0;

if (k === 3) {
big = 10;
} else {
big = 5;
}

// lazily compute the values
if (n < big) {
return lazyGet(n, k-1, memo);
}

var withoutBig = lazyGet(n-big, k, memo);
var withBig = lazyGet(n, k-1, memo);

memo[n][k] = withoutBig + withBig
return memo[n][k];
}


So that was our poor-woman and poor-man universal ‘dynamization’ technique: use the plain recursive algorithm, and plug in some lazy-loading everywhere. Is this cheating? No it’s not. Is this a elegant way? Hmm maybe, maybe not… but it works incredibly well!

## Show Me The Mumbers!

Starting off, ‘mumbers’ is not a word. Now that this is out of the way, let’s indeed look at some numbers. We will want to look at two things:

• The computed answer: we want to make sure our algorithm is still computing the right thing, don’t you agree?
• The number of recursions: we want to see if we’ve made the thing faster.

I’ve copy-pasted the algorithm above with some minor changes into the HTML of this page. Along with some helpers, I’m now saying this:

“Javascript, compute thy numbers!!!”

Here it goes :

That was it.

# If You Want Faster Than A Rockomax, Carry On.

Now that we’ve seen some numbers, we can see a pattern. The number of operations performed changes only every multiple of $5$. That should be a hint that there’s some wastage going on.

Let’s see what the memo array looks like. Now, let me warn you of two things:

• I’m NOT a javascript ninja.
• This code is most likely insane.
• I’m not saying that this is the best possible algorithm, and I don’t care about the best possible algorithm to ~compute change~.
• What follows assume you have a bit more of a brain that the previous part. Which means, I won’t do lengthy explanations of every line.

That was not two but four things, great! Carry on.

Let’s abuse Javascript a little bit and instrument our memo array to make it more convenient to work with. Please close your eyes:

var memo = new Array(n+1);
for (var i = 0; i < memo.length; i++) {
memo[i] = new Array(k+1);
};

memo.lazyGet = function(i, j) {

if (!this[i][j]) {
this[i][j] = getChangeDynamic(i, j);
}
return this[i][j];
}

memo.get = function(i, j) {
return this[i][j];
}

memo.set = function(i, j, val) {
this[i][j] = val
return val; // for chaining
}


Alright, now it will be easier to hack around the algorithm and change things.

## Show Me More Numbers!

We want to see more data! Looking at the memo array for some $n$, we see this:

This thing is filled with unused cells!

We can see that indeed, every non multiple of $5$ is unused. We can thus change every access to the memo array to only use multiples of $5$, like this:

var len = Math.floor(n/5) + 1 // 1-indexed
var memo = new Array(len);
for (var i = 0; i < memo.length; i++) {
memo[i] = new Array(3 + 1); // 1-indexed
};

memo.lazyGet = function(i, j) {
var realI = Math.floor(i/5);

if (!this[realI][j]) {
this[realI][j] = getChangeDynamic(i, j);
}
return this[realI][j];
}

memo.get = function(i, j) {
var realI = Math.floor(i/5);
return this[realI][j];
}

memo.set = function(i, j, val) {
var realI = Math.floor(i/5);
this[realI][j] = val
return val; // for chaining
}


Let’s look at the result :

Wow, that’s much better! But we still see there’s a lot of extra undefined. Let’s remove it by making memo $n \times k-1$, and redirecting all the accesses from j to j-1:

var len = Math.floor(n/5) + 1
var memo = new Array(len);
for (var i = 0; i < memo.length; i++) {
memo[i] = new Array(3);  // remove the extra 1
};

memo.lazyGet = function(i, j) {
var realI = Math.floor(i/5);

if (!this[realI][j-1]) {
this[realI][j-1] = getChangeDynamic(i, j);
}
return this[realI][j-1];
}

memo.get = function(i, j) {
var realI = Math.floor(i/5);
return this[realI][j-1];
}

memo.set = function(i, j, val) {
var realI = Math.floor(i/5);
this[realI][j-1] = val
return val; // for chaining
}


Let’s look at the result :

Cleaned-up that undefined column!

Now we see those silly entries that are invariably $1$. Let’s get rid of them:

var len = Math.floor(n/5)
var memo = new Array(len);   // removed the extra 1
for (var i = 0; i < memo.length; i++) {
memo[i] = new Array(3-1); // removed the extra 1
};

memo.lazyGet = function(i, j) {
var realI = Math.floor(i/5) - 1;

if (realI == -1) { return 1;} // realI will be -1 for access to entry 0
if (j == 1)      { return 1;}

if (!this[realI][j-2]) {
this[realI][j-2] = getChangeDynamic(i, j);
}
return this[realI][j-2];
}

memo.get = function(i, j) {
var realI = Math.floor(i/5) - 1;

var row = this[realI];
if (!row) { return null; }
return row[j-2];
}

memo.set = function(i, j, val) {
var realI = Math.floor(i/5);
this[realI-1][j-2] = val
return val; // for chaining
}


And at last, let’s look at the resulting table:

## How Is This Better Than The First Algorithm?

Let’s compare the original algorithm with the initial dynamic algorithm and this new, shiny one. We compare it’s values with the original recursive only algorithm, but we omit the initial dynamic version (we’ve already shown it equivalent).

Yep, much better! Both the initial getDynamicChange and the optimized one are growing by a factor of $n$. However, the inital one grows by $n/2$ while the optimized one grows by $n/4$. It’s a 100% speed-up.