Rods

rods.js

'use strict';

var prices = {
  1: 1,
  2: 5,
  3: 8,
  4: 9,
  5: 10,
  6: 17,
  7: 17,
  8: 20,
  9: 24,
  10: 30
};

var cache = { };

function best(length) {
  if (length == 0) {
    return {
      items: [],
      total: 0
    };
  }

  if (cache.hasOwnProperty(length)) {
    return cache[length];
  }

  var maxPrice = 0;
  var maxPriceItems = [];
  for (var lengthKey in prices) {
    if (lengthKey > length) {
      break;
    }
    var price = prices[lengthKey];

    var bestRemaining = best(length - lengthKey);
    if (bestRemaining === false) {
      continue;
    }

    var total = price + bestRemaining.total;
    if (maxPrice < total) {
      maxPrice = total;
      maxPriceItems = bestRemaining.items.slice(0);
      maxPriceItems.push(lengthKey);
    }
  }

  if (maxPrice == 0) {
    return false;
  }

  bestRemaining.items = maxPriceItems;
  bestRemaining.total = maxPrice;
  cache[length] = bestRemaining;

  return cache[length];
}

console.log(best(14));