Задача на подумать: подсчёт заданной суммы из элементов массива

const coinChange = function (coins, amount) {
  // test base cases
  if (amount == 0) return 0;
 
  // убираем элементы которые нам точно не пригодятся
  coins = coins.filter((e) => amount >= e);
 
  if (coins.length == 0) return -1;
 
  // без сортировки, достаточно найти только максимум
  const maxVal = Math.max(...coins);
 
  if (maxVal == amount) return 1;
 
  const doubleMaxVal = maxVal * 2;
  // предыдущие значения от которых ведем отсчет
  let dpprev = Array.from({ length: maxVal }, () => ({
      a: new Array(coins.length).fill(0),
      // сумма элементов в массиве чтобы было проще выбирать какую дату оставить
      c: 0,
      // это значение будет использовано для отслеживания устаревания значения 
      sc: doubleMaxVal,
    })),
    // актуальные значения 
    dp = Array.from({ length: maxVal }, () => ({
      a: new Array(coins.length).fill(0),
      // сумма элементов в массиве чтобы было проще выбирать какую дату оставить
      c: 0,
      // это значение будет использовано для отслеживания устаревания значения 
      sc: doubleMaxVal,
    }));
 
  // заполняем массив предыдущих значений
  for (let j = 0; j < coins.length; j++) {
    for (let i = coins[j] - 1, count = 1; i < maxVal; i += 1) {
      if (i - (coins[j] - 1) == 0) {
        if (dpprev[i].c >= count) {
          (dpprev[i].c = 1), (dpprev[i].a[j] = 1);
        } else {
          dpprev[i].c++, dpprev[i].a[j]++;
        }
      } else {
        const prev = dpprev[i - coins[j]];
        if (prev.c) {
          if (dpprev[i].c && prev.c && dpprev[i].c <= prev.c) continue;
          dpprev[i].a = prev.a.slice();
          dpprev[i].a[j]++;
          dpprev[i].c = prev.c + 1;
        }
      }
    }
  }
  // если был элемент равный искомому значению 
  if (amount == maxVal) return dpprev[maxVal - 1].c;
  let imax = 0;
 
  for (let i = maxVal, swapCount = doubleMaxVal; i < amount; i++) {
    if (i == swapCount) {
      const tmp = dpprev;
      dpprev = dp;
      dp = tmp;
      swapCount += maxVal;
    }
    imax = i % maxVal;
    for (let j = 0; j < coins.length; j += 1) {
      const prevIndx = imax - coins[j];
      // определяем где будем искать предыдущее значение
      const prev = prevIndx < 0 ? dpprev[maxVal + prevIndx] : dp[prevIndx];
      if (prev.c) {
        if (dp[imax].c && dp[imax].sc == swapCount && dp[imax].c <= prev.c)
          continue;
        for (let k = 0; k < coins.length; k++) dp[imax].a[k] = prev.a[k];
        dp[imax].a[j]++;
        dp[imax].c = prev.c + 1;
        dp[imax].sc = swapCount;
      }
    }
  }
 
  return dp[imax] == null
    ? -1
    : dp[imax].a.reduce((r, e, i) => {
        r[coins[i]] = e;
        return r;
      }, {});
};
 
 
 
console.log(coinChange([10, 3], 36), 36); // { '3': 2, '10': 3 } 36
console.log(coinChange([474, 83, 404, 3], 264), 264); // { '3': 5, '83': 3 } 264
console.log(coinChange([41, 23, 21, 17, 13], 130), 130); // { '13': 2, '17': 1, '21': 0, '23': 2, '41': 1 } 130
console.log(coinChange([100, 3, 20, 60, 50], 123), 123); // { '3': 1, '20': 0, '50': 0, '60': 2, '100': 0 } 123
 
console.time("mr_dramm");
console.log(coinChange([474, 83, 404, 3], 1000264), 1000264); // { '3': 0, '83': 0, '404': 5, '474': 2106 } 1000264
console.timeEnd("mr_dramm"); // mr_dramm: текущее ~100ms предыдущее было ~200ms

function swapParts(source) {
  const halfLength = source.length / 2;
 
  const firstPart = new Array(halfLength).fill(null);
  const secondPart = source.slice(halfLength);
 
  return secondPart.concat(firstPart);
}
 
// source - { a: number[] - elements, c: number - count }
// source1 - dp[i], source2 - dp[i-coin], j index coin
const memo = (s1, s2, i) => {
  if (s1 && s2) {
    if (s1.c <= s2.c) return { a: s1.a.slice(), c: s1.c };
    const o = { a: s2.a.slice(), c: s2.c };
    o.a[i]++;
    o.c++;
    return o;
  } else if (s1) {
    return { a: s1.a.slice(), c: s1.c };
  } else if (s2) {
    const o = { a: s2.a.slice(), c: s2.c };
    o.a[i]++;
    o.c++;
    return o;
  }
  return null;
};
 
const coinChangeProto = function (coins, amount) {
  // test base cases
  if (amount == 0) return null;
 
  // убираем элементы которые нам точно не пригодятся
  coins = coins.filter((e) => amount >= e);
 
  if (coins.length == 0) return null;
 
  // без сортировки, достаточно найти только максимум
  const maxVal = Math.max(...coins);
  const doubleMaxVal = maxVal * 2;
  let dp = new Array(doubleMaxVal).fill(null);
 
  // готовим массив длинной max coin val * 2 для подсчета сумм
  // но заполняем только опервую половину
  for (let j = 0; j < coins.length; j++) {
    for (let i = coins[j] - 1; i < maxVal; i += 1) {
      if (i - (coins[j] - 1) == 0) {
        //dp[i] = Math.min(dp[i], 1);
        // создаем дату с массивом и суммой элементов в массиве чтобы было проще выбирать какую дату оставить
        // не тратить на подсчет тики
        dp[i] = memo(dp[i], { a: new Array(coins.length).fill(0), c: 0 }, j);
      } else {
        // dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        dp[i] = memo(dp[i], dp[i - coins[j]], j);
      }
    }
  }
 
  let imax = 0;
  for (let i = maxVal, swapCount = doubleMaxVal; i < amount; i++) {
    if (i == swapCount) {
      dp = swapParts(dp);
      swapCount += maxVal;
    }
    imax = (i % maxVal) + maxVal;
    for (let j = 0; j < coins.length; j += 1) {
      // dp[imax] = Math.min(dp[imax], dp[imax - coins[j]] + 1);
      dp[imax] = memo(dp[imax], dp[imax - coins[j]], j);
    }
  }
 
  return dp[imax] == null
    ? -1
    : dp[imax].a.reduce((r, e, i) => {
        r[coins[i]] = e;
        return r;
      }, {});
};
 
console.log(coinChangeProto([10, 3], 36)); // { '3': 2, '10': 3 }
console.log(coinChangeProto([474, 83, 404, 3], 264)); // { '3': 5, '83': 3 }
console.log(coinChangeProto([41, 23, 21, 17, 13], 130)); // { '13': 2, '17': 1, '21': 0, '23': 2, '41': 1 }
console.log(coinChangeProto([100, 3, 20, 60, 50], 123)); // { '3': 1, '20': 0, '50': 0, '60': 2, '100': 0 }
 
console.time("mr_dramm");
console.log(coinChangeProto([474, 83, 404, 3], 1000264), 1000264); // { '3': 0, '83': 0, '404': 5, '474': 2106 } 1000264
console.timeEnd("mr_dramm"); // mr_dramm: ~200ms

const coinChange = function (coins, amount) {
  // test base cases
  if (amount == 0) return 0;
 
  // убираем элементы которые нам точно не пригодятся
  coins = coins.filter((e) => amount >= e);
 
  if (coins.length == 0) return -1;
 
  // без сортировки, достаточно найти только максимум
  const maxVal = Math.max(...coins);
 
  // базовый случай когда одно из значений в coins равно amount
  if (maxVal == amount)
    return coins.reduce((r, e, i) => {
      if (e == maxVal) r[e] = 1;
      else r[e] = 0;
      return r;
    }, {});
 
  const doubleMaxVal = maxVal * 2;
  // предыдущие значения от которых ведем отсчет
  let dpprev = Array.from({ length: maxVal }, () => ({
      a: new Array(coins.length).fill(0),
      // сумма элементов в массиве чтобы было проще выбирать какую дату оставить
      c: 0,
      // это значение будет использовано для отслеживания устаревания значения
      sc: doubleMaxVal,
    })),
    // актуальные значения
    dp = Array.from({ length: maxVal }, () => ({
      a: new Array(coins.length).fill(0),
      // сумма элементов в массиве чтобы было проще выбирать какую дату оставить
      c: 0,
      // это значение будет использовано для отслеживания устаревания значения
      sc: doubleMaxVal,
    }));
 
  // заполняем массив предыдущих значений, от минимального до максимального, на этом шаге задача не будет решена
  // так как предварительно мы уже проверили наличие максимального элемента в массиве
  for (let j = 0; j < coins.length; j++) {
    for (let i = coins[j] - 1, count = 1; i < maxVal; i += 1) {
      if (i - (coins[j] - 1) == 0) {
        if (dpprev[i].c >= count) {
          (dpprev[i].c = 1), (dpprev[i].a[j] = 1);
        } else {
          dpprev[i].c++, dpprev[i].a[j]++;
        }
      } else {
        const prev = dpprev[i - coins[j]];
        if (prev.c) {
          if (dpprev[i].c && prev.c && dpprev[i].c <= prev.c) continue;
          dpprev[i].a = prev.a.slice();
          dpprev[i].a[j]++;
          dpprev[i].c = prev.c + 1;
        }
      }
    }
  }
  // основной цикл решения проблемы
  let imax = 0;
  let swapCount = doubleMaxVal;
  for (let i = maxVal; i < amount; i++) {
    if (i == swapCount) {
      const tmp = dpprev;
      dpprev = dp;
      dp = tmp;
      swapCount += maxVal;
    }
    imax = i % maxVal;
    for (let j = 0; j < coins.length; j += 1) {
      const prevIndx = imax - coins[j];
      // определяем где будем искать предыдущее значение
      const prev = prevIndx < 0 ? dpprev[maxVal + prevIndx] : dp[prevIndx];
      if (!prev.c) continue;
 
      if (dp[imax].c && dp[imax].sc == swapCount && dp[imax].c <= prev.c)
        continue;
      for (let k = 0; k < coins.length; k++) dp[imax].a[k] = prev.a[k];
      dp[imax].a[j]++;
      dp[imax].c = prev.c + 1;
      dp[imax].sc = swapCount;
    }
  }
  if (dp[imax].sc == swapCount)
    return dp[imax].a.reduce((r, e, i) => {
      r[coins[i]] = e;
      return r;
    }, {});
  return -1;
};
// значение max равное amount
console.log(coinChange([3, 36], 36), 36); // { '3': 0, '36': 1 } 36
console.log(coinChange([1], 1), 1); // { '1': 1 } 1
 
console.log(coinChange([10, 15], 36), 36); // -1
 
console.log(coinChange([3, 10], 36), 36); // { '3': 2, '10': 3 } 36
console.log(coinChange([474, 83, 404, 3], 264), 264); // { '3': 5, '83': 3 } 264
console.log(coinChange([41, 23, 21, 17, 13], 130), 130); // { '13': 2, '17': 1, '21': 0, '23': 2, '41': 1 } 130
console.log(coinChange([100, 3, 20, 60, 50], 123), 123); // { '3': 1, '20': 0, '50': 0, '60': 2, '100': 0 } 123
 
console.time("mr_dramm");
console.log(coinChange([474, 83, 404, 3], 1000264), 1000264); // { '3': 0, '83': 0, '404': 5, '474': 2106 } 1000264
console.timeEnd("mr_dramm"); // mr_dramm: текущее ~100ms предыдущее было 200ms