Примеры

Получение числа Фибоначчи

Задача: F(n) = F(n-1) + F(n-2), где F(0) = 0, F(1) = 1
Проблема: прямая рекурсия имеет сложность O(2ᴺ)

Решение сверху вниз - мемоизация

function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (!memo.has(n)) {
    memo.set(n, fib(n - 1, memo) + fib(n - 2, memo));
  }
  return memo.get(n);
}
console.log(fib(10)); // 55

Решение снизу вверх - табличное решение

function fib(n) {
  if (n <= 1) return n;
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
console.log(fib(10)); // 55

Количество способов размена монет (Number of Ways to Make Change)

Нужно найти количество различных способов составить сумму размена монет для выдачи сдачи.
Пример: coins = [1, 2, 5], amount = 5. Ответ: 4 (1+1+1+1+1, 1+1+1+2, 1+2+2, 5).

// Функция для решения задачи с торговым автоматом
// coins: доступные номиналы монет, paid: внесенная сумма, price: цена товара
function vendingMachine(coins, paid, price) {
  // Вычисляем сумму сдачи
  const change = paid - price;
  // Если сдача отрицательная, значит денег недостаточно
  if (change < 0) return "Недостаточно денег";

  // Создаем массив dp размером change + 1, заполненный бесконечностями
  // dp[i] будет хранить минимальное количество монет для суммы i
  const dp = new Array(change + 1).fill(Infinity);
  // Базовый случай: для сдачи 0 нужно 0 монет
  dp[0] = 0;

  // Перебираем все суммы от 1 до change
  for (let i = 1; i <= change; i++) {
    // Для каждой суммы i перебираем все доступные монеты
    for (const coin of coins) {
      // Если монета не больше текущей суммы, её можно использовать
      if (coin <= i) {
        // Обновляем dp[i]: минимум между текущим значением и
        // "использованием текущей монеты + оптимальное решение для i - coin"
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  // Если dp[change] осталось Infinity, значит нет подходящих монет
  if (dp[change] === Infinity) return "Нет подходящих монет";

  // Восстанавливаем список использованных монет
  const usedCoins = [];
  // remaining - оставшаяся сумма, которую нужно разменять
  let remaining = change;

  // Пока есть что разменивать
  while (remaining > 0) {
    // Сортируем монеты по убыванию, чтобы начать с самых крупных
    // Это оптимизация для быстрого восстановления решения
    for (const coin of coins.sort((a, b) => b - a)) {
      // Проверяем две вещи:
      // 1. Монета не больше оставшейся суммы
      // 2. Использование этой монеты ведет к оптимальному решению
      //    (это проверяется сравнением dp[remaining] и dp[remaining - coin] + 1)
      if (coin <= remaining && dp[remaining] === dp[remaining - coin] + 1) {
        // Добавляем монету в список использованных
        usedCoins.push(coin);
        // Уменьшаем оставшуюся сумму
        remaining -= coin;
        // Выходим из цикла, так как монету нашли
        break;
      }
    }
  }

  // Возвращаем строку с описанием сдачи
  // usedCoins.join('¢ + ') соединяет монеты через ' + ' и добавляет '¢' к каждой
  return `Сдача ${change}¢: ${usedCoins.join("¢ + ")}¢`;
}

// Тестовые случаи
console.log(vendingMachine([1, 5, 10, 25], 100, 70)); // Сдача 30¢: 25¢ + 5¢
console.log(vendingMachine([1, 5, 10, 25], 50, 35)); // Сдача 15¢: 10¢ + 5¢
console.log(vendingMachine([5, 10, 25], 30, 25)); // Сдача 5¢: 5¢
console.log(vendingMachine([5, 10, 25], 10, 25)); // Недостаточно денег
console.log(vendingMachine([5, 10, 25], 26, 1)); // Нет подходящих монет