Dynamic Programming

The Robber Problem

Imagine that you are a burglar planning a heist. Your target is the National Museum, a gallery filled with precious art, artifacts, and dinosaur bones. Your mission is to confiscate as many of the exhibits as possible. The constraint, however, is that you may not loot adjacent rooms. Doing so will trigger the security system and blow your cover.

Given a list of non-negative integers that represent the value of each exhibit, what is the maximum amount of money you can expect from your heist?

For Example

Let's try this list: [5, 3]

When the list is short, our choice is straightforward; we'll take the larger of the two values, $5. But what if there's a third value? [5, 3, 7]

With that, we can either take 5+7 or 3. So, 5+7 ($12) is the answer.

Let's add a fourth: [5, 3, 7, 10]

Now, there are three choices:

1. 5+7 = $12
2. 5+10 = $15
3. 3+10 = $10

Do we skip one value or two? Here, the answer is to skip two (3 and 7). The next question is: how do you do this programmatically for a list of size n?

My Solution

function calculateMaxPath(exhibits) {
    var loot = 0,
        paths = [];

    // For each of the exhibits
    for (var i in exhibits) {
        // Determine the value from 2 and 3 spots back
        var back2 = (i-2 < 0) ? 0 : paths[i-2],
            back3 = (i-3 < 0) ? 0 : paths[i-3];

        // Best path = current value + better of 2 vs 3 back
        var maxPath = exhibits[i] + Math.max(back2, back3);

        // Add the best path to the list of paths
        paths.push(maxPath);

        // Determine if it's the best path seen so far
        loot = Math.max(loot, maxPath);
    }

    // Return maximum loot
    return loot;

}

// Unit Tests
console.assert(calculateMaxPath([]) == 0);
console.assert(calculateMaxPath([5]) == 5);
console.assert(calculateMaxPath([5,3]) == 5);
console.assert(calculateMaxPath([5,3,7]) == 12);
console.assert(calculateMaxPath([5,3,7,10]) == 15);
console.assert(calculateMaxPath([14,11,23,7,27,22]) == 64);