Dynamic Programming Bottoms up approach clarification

Question

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];

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 '21 at 01:16
See also [What is the difference between memoization and dynamic programming?](https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming) — ggorlen, Apr 12 '21 at 01:21

score 0 · Answer 1 · answered Apr 12 '21 at 02:28

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)

Dynamic Programming Bottoms up approach clarification

1 Answers1