0

So I have been really trying to grasp Dynamic Programming. I can say that I really understand the memoization top down approach, but the bottoms up approach is really confusing to me. I was able to solve rods cutting top down, but I had to seek the solution for the bottoms up. I just don't understand when to use a 1D array or a 2D array. Then the for loop within the bottoms up is just confusing. Can anyone help me understand the differences in these two codes conceptually?

// Top Down Memoizaton: 

const solveRodCuttingTop = function(lengths, prices, n) {
  return solveRodCuttingHelper(0, lengths, prices, n); 
};

function solveRodCuttingHelper(idx, span, prices, n, memo = []) {
  // BASE CASES 
  if (idx === span.length || n <= 0 || prices.length !== span.length) {
    return 0;
  }
  let included = 0, excluded = 0; 
  memo[idx] = memo[idx] || []; 

  if (memo[idx][n] !== undefined) return memo[idx][n]; 

  if (span[idx] <= n) {
    included = prices[idx] + solveRodCuttingHelper(idx, span, prices, n - span[idx], memo);
  }

  excluded = solveRodCuttingHelper(idx + 1, span, prices, n, memo);

  memo[idx][n] = Math.max(included, excluded); 
  
  return memo[idx][n];
}



// Bottoms up 
const solveRodCuttingBottom = function(lengths, prices, n) {
  const rods = Array.from({length: n + 1});
  rods[0] = 0; 
  let maxRevenue = - Infinity;

  for (let i = 1; i < rods.length; i++) {
    for (let j = 1; j <= i; j++) {
      maxRevenue = Math.max(maxRevenue, prices[j - 1] + rods[i - j])
    }
    rods[i] = maxRevenue
  }
  return rods[prices.length];
};

const lengths = [1, 2, 3, 4, 5];
const prices = [2, 6, 7, 10, 13];

2
  • What's confusing exactly? For TD, you say: "I can't solve this problem because it's too big. I need to solve smaller problems first and build up to the big solution". For BU you say: "I start by solving smaller problems and build up to the big solution". Either way, you wind up solving small problems first and building to large ones, it's just a matter of where you start. Memo hash and DP table are two ways to store the subproblem solutions so far.
    – ggorlen
    Apr 12, 2021 at 1:16
  • 1

1 Answer 1

0

This is an interesting problem. Maybe I'm over-simplifying it, but if you first calculate each price per length, you can determine the solution by selling as much as possible at the highest rate. If the remaining rod is too short to sell at the best rate, move onto the next best rate and continue.

To solve using this technique, we first implement a createMarket function which takes lenghts and prices as input, and calculates a price-per-length rate. Finally the market is sorted by rate in descending order -

const createMarket = (lengths, prices) =>
  lengths.map((l, i) => ({
    length: l,                      // length
    price: prices[i],               // price
    rate: prices[i] / l             // price per length
  }))
  .sort((a, b) => b.rate - a.rate)  // sort by price desc

const lengths = [1, 2, 3, 4, 5]
const prices = [2, 6, 7, 10, 13]

console.log(createMarket(lengths, prices))
[
  { length: 2, price: 6, rate: 3 },
  { length: 5, price: 13, rate: 2.6 },
  { length: 4, price: 10, rate: 2.5 },
  { length: 3, price: 7, rate: 2.3333333333333335 },
  { length: 1, price: 2, rate: 2 }
]

Next we write recursive solve to accept a market, [m, ...more], and a rod to cut and sell. The solution, sln, defaults to [] -

const solve = ([m, ...more], rod, sln = []) =>
  m == null
    ? sln
: m.length > rod
    ? solve(more, rod, sln)
: solve([m, ...more], rod - m.length, [m, ...sln])

const result =
  solve(createMarket(lengths, prices), 11)

console.log(result)
[
  { length: 1, price: 2, rate: 2 },
  { length: 2, price: 6, rate: 3 },
  { length: 2, price: 6, rate: 3 },
  { length: 2, price: 6, rate: 3 },
  { length: 2, price: 6, rate: 3 },
  { length: 2, price: 6, rate: 3 }
]

Above, solve returns the rod lengths that sum to the maximum price. If you want the total price, we can reduce the result and sum by price -

const bestPrice =
  solve(createMarket(lengths, prices), 11)
    .reduce((sum, r) => sum + r.price, 0)

console.log(bestPrice)
32

Not the answer you're looking for? Browse other questions tagged or ask your own question.