Кількість розв’язків комбінаторних задач (DP)

Повне пояснення

Коротке пояснення

Алгоритм підраховує кількість способів скласти задану суму, використовуючи доступні елементи (наприклад, монети). Він працює за принципом динамічного програмування: розв’язує підзадачі, зберігає їх у таблиці і використовує вже знайдені результати.

Аналогія

Уявіть, що ви збираєте пазл: кожен шматок – це елемент, а ціль – повна картинка. Ви зберігаєте вже складені частини, щоб не повторювати роботу.

Коли застосовувати

• Потрібно знайти кількість способів скласти суму з набору чисел.
• Підхід підходить для задач типу «монети» або «розбиття числа».
• Вхід – масив елементів і цільове число.
• Результат – ціле число, що дорівнює кількості розв’язків.
• Підходить для невеликих до середніх розмірів даних.

Кроки алгоритму

1. Ініціалізувати масив dp довжиною target+1, встановити dp[0] = 1.
2. Для кожного елемента в coins:
   • Перебрати всі суми від coin до target.
   • Оновити dp[sum] += dp[sum - coin].
3. Після завершення повернути dp[target].

Візуальна інтуїція (текстова)

coins = [1, 2]
target = 4

dp:   0 1 2 3 4
init: 1 0 0 0 0
after coin=1:
      1 1 1 1 1
after coin=2:
      1 1 2 2 3
result = dp[4] = 3

Складність

• Часова складність: O(n * target), де n – кількість елементів.
• Пам’ятна складність: O(target).

Код (js)

// Функція підраховує кількість способів скласти target з coins
function countWays(coins, target) {
  // Ініціалізуємо масив dp довжиною target+1
  const dp = new Array(target + 1).fill(0);
  // Є один спосіб отримати суму 0 – не брати жодного елемента
  dp[0] = 1;

  // Проходимо по кожному елементу coins
  for (const coin of coins) {
    // Для кожної суми від coin до target
    for (let sum = coin; sum <= target; sum++) {
      // Додаємо кількість способів досягти (sum - coin)
      dp[sum] += dp[sum - coin];
    }
  }

  // Повертаємо кількість способів досягти target
  return dp[target];
}

// Тестовий приклад
console.log(countWays([1, 2], 4)); // очікуваний результат: 3

Типові помилки і поради

1. Не ініціалізувати dp[0] = 1 – без цього алгоритм поверне 0 для будь-якої суми.
2. Перевірити порядок циклів – внутрішній цикл має починатися з coin, а не 0.
3. Використовувати неправильний тип даних – dp повинен бути масивом чисел, а не об’єктами.
4. Не враховувати великий target – для дуже великих сум використовуйте BigInt або модуль.
5. Оптимізація – якщо coins мають однакові значення, можна уникнути дублювання.

Перевір себе

1. Що означає dp[0] = 1 у цьому алгоритмі?
2. Яка складність пам’яті і чому вона така?