4.9 Dynamic Programming

In computer science, you may face a kind of problem called optimization problem. We can define it as a problem that require to select the best element with regard to some criterion from some set of available alternatives. For example, find the shortest path between two points. In this book, we will explore several different problem solving strategies for the kind of problems. Dynamic programming is one of this strategy.

Suppose you are programming a vending machine. You have to find a way to make change using minimum number of coins. If a customer puts in an euro bill and purchases an item for 37 cents, what is the smallest number of coins you can use to make change? The answer is 4 coins: one of 50 cents, one of 10, one of 2 and one cent pieces. To arrive to this result, start with the largest coin available (50 cents) and use as many of those as possible. Then we go to the next lowest coin value and use as many of those as possible. This approach is called a greedy method because we treats the solution as some sequence of steps and picks the locally optimal choice at each step. But a greedy algorithm does not guarantee an optimal solution. Picking locally optimal choices may result in a bad global solution.
What if our vending machines is used in Lower Elbonia where they have a 21 cent coin? In the previous exemple, with the greedy method we would still find the solution to be four coins. However, the optimal answer is three coins of 21 cent.

The dynamic programming (or dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space.

This kind of algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Note that some greedy algorithms (such as Kruskal's or Prim's for minimum spanning trees) are proven to lead to the optimal solution.

function giveBackChange(coinValueList, change) {
   var minCoins = change;
   if (coinValueList.includes(change)) {
     return 1;
   }
   else {
      for (var i = 0; i < array.length; i++) {

      }
   }

   return minCoins;
}

console.log( giveBackChange([1, 5, 10, 25], 63) );