Rod cutting

dynamic programming rod cutting

by Augustus Yuan

JavaScript

function calcOptimalCutRod(prices, size) {
  // start off with zero since the 0 size means 0 cuts
  var values = [0];
  
  // going through the list of prices all the way to the size
  for (let i=1; i <= size; i++) {
    // set the lowest possible number
    var maxVal = Number.MIN_SAFE_INTEGER;
    // for every cut size, compare the price value and take the max
    // we store in the `values` previously computed values to avoid
    // recalculation (memoization)
    for (let j=0; j < i; j++) {
      maxVal = Math.max(maxVal, prices[j] + values[i-j-1]);
      values[i] = maxVal;
    }
  }
  console.log(values);
  return values[size];
}

var prices = [1, 5, 8, 9, 10, 17, 17, 20];
console.log(calcOptimalCutRod(prices, prices.length));