DynamicProgramming1.js

/*Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way that
they sum up to S.

Given coins with values 1, 3, and 5. And the sum S is set to be 9.
Given coins with values 1, 3, and 5. And the sum S is set to be 10.
Given coins with values 1, 3, and 5. And the sum S is set to be 11.
Given coins with values 1, 3, and 5. And the sum S is set to be 20.

*/
(function () {

  function minOfCoins(v, s) {
    var min = new Array(s + 1).fill(Infinity),
      lst = 0,
      i = 0,
      j = 0;
    min[0] = 0;
    for (; i <= s; i = i + 1) {

      for (j = 0; j < v.length; j = j + 1) {
        lst = min[i - v[j]] + 1 || 0;
        if (v[j] <= i && lst < min[i]) {
          min[i] = lst;
        }
      }
    }
    return min[s];
  }

  console.log(minOfCoins([1, 3, 5], 9));
  console.log(minOfCoins([1, 3, 5], 10));
  console.log(minOfCoins([1, 3, 5], 12));
  console.log(minOfCoins([1, 3, 5], 20));
})();