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[0]);

    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);
}