Dynamic Programming is a powerful tool in solving algorithms. You basically take a problem, and attack it by saying that it’s the outcome of solving its sub-problems. In a way, it’s no different than the Divide and Conquer approach for recursive calls, except that you remember the results of solving those sub-problems as you go along so that you won’t end up having to solve them again. Let’s take a look at an example.

``````// Problem: You are given two arrays of equal length, each representing an assembly line. Each index represents
// a station in the line. The value at each index represents the cost of transferring the machine from
// the previous station. Of course, putting the machine into the line in the first place carries a cost
// in itself. Write a function that returns an array representing the transfer costs per station of the
// path that involves the least transfer cost overall.
// e.g.

var entryA = 3;
var entryB = 7;
var lineA = [4,5,8,10,5];
var lineB = [9,2,6,3,7];
function fastestPathOverall(entryA,entryB,lineA,lineB);

// #=> [16,18,24,27,32]
``````

We start by saying that the fastestPathOverall is basically a function of the minimum between the values of the fastestPathLineA and fastestPathLineB.

``````function fastestPathOverall(entryA,entryB,lineA,lineB) {
...
return minimumPath(fastestPathA,fastestPathB);
}
``````

In both fastestPathA and fastestPathB, we iterate through their respective lines, proceeding using the station with the smallest transfer cost. The station we need is basically a function of the minimum between proceeding in the same line and transferring to the other.

``````function fastestPathA() {
var path = [];
path.push(entryA);

for(var i=0; i < lineA.length; i++) {
...
var next = minimumValue(directLineA,transferLineA);
path.push(next);
``````

directLineA and transferLineA are simply functions of the last station in our trail of breadcrumbs and the station that we’re considering.

``````      ...
function directLineA() {
var len = path.length
return path[len-1] + lineA[i];
}

function transferLineA() {
var len = path.length
return path[len-1] + lineB[i];
}
...
``````

The final components for our solution are the helper functions we use for comparing stations and paths.

``````  function minimumValue(a,b) {
if (a() < b()) {
return a();
} else {
return b();
}
}

function minimumPath(a,b) {
function sum(arr) {
function callback(m,n) {
return m + n;
}
return Array.prototype.reduce(arr,callback);
}

if (sum(a) > sum(b)) {
return a();
} else {
return b();
}
}
``````

And here’s the complete solution:

``````function fastestPathOverall(entryA,entryB,lineA,lineB) {
function minimumValue(a,b) {
if (a() < b()) {
return a();
} else {
return b();
}
}

function minimumPath(a,b) {
function sum(arr) {
function callback(m,n) {
return m + n;
}
return Array.prototype.reduce(arr,callback);
}

if (sum(a) > sum(b)) {
return a();
} else {
return b();
}
}

function fastestPathA() {
var path = [];
path.push(entryA);

for(var i=0; i < lineA.length; i++) {
function directLineA() {
var len = path.length
return path[len-1] + lineA[i];
}

function transferLineA() {
var len = path.length
return path[len-1] + lineB[i];
}

var next = minimumValue(directLineA,transferLineA);
path.push(next);
}

return path;
}

function fastestPathB() {
var path = [];
path.push(entryB + lineB);

for(var i=1; i < lineB.length; i++) {
function directLineB() {
var len = path.length
return path[len-1] + lineB[i];
}

function transferLineB() {
var len = path.length
return path[len-1] + lineA[i];
}
var next = minimumValue(directLineB,transferLineB);
path.push(next);
}

return path;
}
return minimumPath(fastestPathA,fastestPathB);
}
``````