Understanding Dynamic Programming using Javascript

What are the benefits?

The Rod Cutting Problem

Solve the problem by hand

/**
*
* @param {number[]} prices
* @param {number} length
* @returns {number
*
function cutRod(prices, length) {
if (length <= 0) return 0;
let max = -Infinity;
for (let i = 0; i < length; i ++) {
max = Math.max(max, prices[i] + cutRod(prices, length - i - 1));
}
return max;
}

Top-Down and Bottom-Up

Top-Down in action

/**
*
* @param {number[]} prices
* @param {number} length
* @param {object} memo
*/
const cutRodMemoized = (prices, length, memo) => {
if (typeof memo[length] === "number") return memo[length];
if (length <= 0) return memo[length] = 0;
let max = -Infinity;
for (let i = 0; i < length; i ++) {
max = Math.max(max, prices[i] + cutRodMemoized(prices, length - i - 1, memo));
}
return memo[length] = max;
}
/**
*
* @param {number[]} prices
* @returns {number}
*/
function cutRod(prices) {
const memo = {};
const length = prices.length;
return cutRodMemoized(prices, length, memo);
}

Bottom-Up in action

/**
*
* @param {number[]} prices
* @returns {number}
*/
function cutRod(prices) {
const table = Array(prices.length + 1);
table[0] = 0;
for (let i = 1; i <= prices.length; i ++) {
let max = -Infinity;
for (let j = 0; j < i; j ++) {
max = Math.max(max, prices[j] + table[i - j - 1]);
}
table[i] = max;
}
return table[prices.length];
}
max = Math.max(max, prices[j] + table[i - j - 1]);

Further work

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store