Solve Complex Problems in JavaScript with Dynamic Programming

Share this video with your friends

Send Tweet

Every dynamic programming algorithm starts with a grid. It entails solving subproblems and builds up to solving the big problem. Let’s break down a problem and solve it in pieces using dynamic programming with JavaScript.

Eduardo  Cancino
Eduardo Cancino
~ 6 years ago
function createGrid() {
  let newGrid = []
  for (let row = 0; row < items.length; row++) {
    newGrid[row] = []
    for (let col = 0; col < constraint.length; col++) {
      newGrid[row][col] = 0
    }
  }
  return newGrid
}

vs

function createGrid(items, constraint) {
  return items.map(item => constraint.map(() => 0))
}
namrata1695
namrata1695
~ 2 years ago

I am doubtful about the statement : Dynamic programming only works when each sub-problem doesn't depend on other sub-problems. In the example shown above, in case of tent, food, why do we take values from above cell , then ?

Zac Jones
Zac Jones
~ 2 years ago

@namrata1695, I don't have a specific answer to your question but another example of dynamic programming might help clarify Tyler's opinion: https://www.geeksforgeeks.org/travelling-salesman-problem-using-dynamic-programming/