Dynamic Programming Solution in JS

coinChange.js

// Coin Change - Minimum number of coins

function coinChange(coins, W) {
  let cache = [0];
  for (let j = 1; j <= W; j++) {
    cache[j] = Number.MAX_VALUE;
  }

  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= W; j++) {
      cache[j] = Math.min(cache[j - coins[i]] + 1, cache[j]);
    }
  }
  return cache[W] == Number.MAX_VALUE ? -1 : cache[W];
}

console.log(coinChange([2,5,10,1],27)); // 4

coinChange2.js

// Coin Change 2 - Number of ways

function coinChange2(coins, W) {
  let cache = [1];

  for (let j = 1; j <= W; j++) {
    cache[j] = 0;
  }

  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= W; j++) {
      cache[j] = cache[j] + cache[j - coins[i]];
    }
  }
  return cache[W];
}

console.log(coinChange2([2, 7, 13], 500)); // 717

lcs.js

// Longest Common Subsequence

function lcs(s1, s2) {
  let cache = [];
  for (let i = -1; i < s1.length; i++) {
    cache[i] = [];
    for (let j = -1; j < s2.length; j++) {
      cache[i][j] = 0;
    }
  }

  for (let i = 0; i < s1.length; i++) {
    for (let j = 0; j < s2.length; j++) {
      if (s1[i] === s2[j]) {
        cache[i][j] = cache[i - 1][j - 1] + 1;
      } else {
        cache[i][j] = Math.max(cache[i - 1][j], cache[i][j - 1]);
      }
    }
  }
  return cache[s1.length - 1][s2.length - 1];
}

console.log(lcs("AGGTAB", "GXTXAYB"));

lis.js

// Longest Increasing Subsequence

function lis(s) {
if (s.length == 0) return 0;
  let cache = [];
    
  let result = 1;

  for (let i = 0; i < s.length; i++) {
    cache[i] = 1;
    for (let j = i - 1; j >= 0; j--) {
      if (s[i] > s[j] && cache[j] + 1 > cache[i]) {
        cache[i] = cache[j] + 1;
        if (cache[i] > result) result = cache[i]; 
      }
    }
  }

  return result;
}

console.log(lis([10, 1, 5, 6, 2, 3, 4]));

maxKnapsack.js

// Knapsack 0-1, Knapsack multiple

function maxKnapsack(weights, values, W, multiple = false) {
  let cache = [];
  for (let i = -1; i < weights.length; i++) {
    cache[i] = [];
    for (let j = 0; j <= W; j++) {
      cache[i][j] = 0;
    }
  }

  for (let i = 0; i < weights.length; i++) {
    for (let j = 1; j <= W; j++) {
      if (weights[i] <= j) {
        let included = values[i] + cache[i - 1 + multiple * 1][j - weights[i]];
        let excluded = cache[i - 1][j];
        cache[i][j] = Math.max(included, excluded);
      } else cache[i][j] = cache[i - 1][j];
    }
  }
  return cache[weights.length - 1][W];
}

console.log(maxKnapsack([12, 2, 1, 1, 4], [4, 2, 1, 2, 10], 15, true));