Skip to main content

Чому важливо правильно обрати стан у динамічному програмуванні?

АлгоритмиJunior~3 хв читання
Запропонувати правку

Коротка відповідь

  • Стан визначає, які підзадачі ви розв'язуєте і як повторно використовуються їхні результати.
  • Правильний стан забезпечує коректність (немає пропусків і подвійного підрахунку) та прозорі переходи.
  • Від нього напряму залежать асимптотика за часом/пам'яттю та можливість оптимізацій (стиснення вимірів, монотонності).
  • Неправильний стан часто призводить до експоненти, складних або некоректних переходів і неможливості відновити відповідь.

Розгорнута відповідь

Що таке стан у ДП

Стан - це мінімальний набір параметрів, який однозначно описує підзадачу так, щоб її розв'язок можна було повторно використати. У таблиці/кеші ми зберігаємо цільову метрику (мінімум, максимум, кількість, булеве значення досяжності) для цього набору параметрів.

Чому вибір стану критичний

  • Коректність: стан повинен містити рівно ту інформацію, яка впливає на майбутні рішення. Недостатній - веде до пропуску валідних рішень; надлишковий - до подвійного підрахунку і зайвих вимірів.
  • Прості переходи: добре обраний стан дає локальні й детерміновані переходи. Поганий - змушує «озиратися назад» далеко або перебирати історію.
  • Складність: розмірність і діапазони параметрів стану визначають розмір таблиці ДП і кількість переходів (O(кількість_станів × переходів_на_стан)).
  • Оптимізації: правильне формулювання часто дає змогу скоротити пам'ять (стиснення до 1D), використати монотонності, бінарний пошук, deque-оптимізації.
  • Відновлення відповіді: якщо потрібно відновлювати рішення, стан має дозволяти зберігати «вказівники» переходів.

Як обирати стан: чек-лист

  1. Сформулюйте рішення як послідовність виборів: який наступний вибір робить алгоритм?
  2. Визначте мінімальний контекст, що впливає на наступний вибір (позиція i, залишковий ресурс, останній елемент/баланс/маска тощо).
  3. Перевірте, що перехід з цього контексту не потребує «історії», не включеної в стан.
  4. Оцініть розмірність і діапазони: чи можна звузити параметри або переформулювати метрику, зберігши оптимальність (інваріанти, «мінімальний останній» тощо).
  5. Визначте порядок обходу (ітеративний/топологічний) та базові випадки.
  6. Подумайте про відновлення відповіді та стиснення пам'яті заздалегідь.

Приклад 1: 0/1 Рюкзак - правильний стан

Задача: максимізувати сумарну цінність при місткості W. Правильний стан: dp[i][w] - найкраща цінність, розглядаючи перші i предметів при ємності w. Перехід враховує два варіанти: взяти/не взяти i-й предмет.

def knapsack_01(values, weights, W): n = len(values) # 1D-стиснення по w: порядок w від W до 0, щоб не використовувати предмет багаторазово dp = [0] * (W + 1) for i in range(n): wi, vi = weights[i], values[i] for w in range(W, wi - 1, -1): dp[w] = max(dp[w], dp[w - wi] + vi) return dp[W] # Стану (w) достатньо, тому що "i" закладено в напрямку обходу; # неправильний стан без w (наприклад, лише сума цінності) не дає змоги перевіряти обмеження і призводить до некоректних переходів.

Приклад 2: LIS - неправильний vs правильний стан

Найдовша зростаюча підпослідовність (LIS). Наївна спроба помилкового стану: dp[k] = «чи існує зростаюча підпослідовність довжини k». Цей стан не зберігає останній елемент, тож неможливо коректно визначити, чи можна продовжити підпослідовність поточним числом - доведеться перебирати всі варіанти (експонента або складні структури).

# Погана ідея (ілюстрація, не використовуйте): # dp[k] = True/False, чи існує зростаюча підпослідовність довжини k # Не знаючи останнього елемента, не можна перевірити a[i] > last, тому перехід невизначений. pass

Правильний 1: dp[i] - довжина LIS, що закінчується на i. Перехід: dp[i] = 1 + max(dp[j] : j < i і a[j] < a[i]), інакше 1. Це O(n^2).

def lis_n2(a): n = len(a) dp = [1] * n # dp[i] - LIS, що закінчується на i for i in range(n): for j in range(i): if a[j] < a[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp, default=0)

Правильний 2 (оптимізований стан): tails[k] - мінімально можливий останній елемент зростаючої підпослідовності довжини k+1. Це вже інша метрика в стані, але вона достатня для коректних переходів і дає O(n log n).

import bisect def lis_nlogn(a): tails = [] # tails[k] - мінімальний останній елемент для довжини k+1 for x in a: i = bisect.bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails)

Зауваження: в обох рішеннях стан містить мінімально необхідну інформацію для валідного переходу: або вказівку «де закінчуємо» (dp[i]), або «який мінімальний хвіст маємо на кожну довжину» (tails).

Типові помилки під час вибору стану

  • Недостатній стан: не зберігає ключовий фактор (останній елемент, залишковий ресурс, баланс). Підсумок - некоректні або експоненційні переходи.
  • Надлишковий стан: додано параметри, які не впливають на майбутнє рішення (зайва історія), що роздмухує таблицю і час.
  • Неправильний порядок обходу: стан обрано вірно, але обчислюється до того, як готові всі залежності.
  • Відсутність інваріантів: метрика в стані не підтримує монотонності/мінімальності, що позбавляє оптимізацій.

Коротка пам'ятка

  • Стан = мінімальний контекст, що впливає на наступний крок.
  • Переходи локальні і не потребують додаткової історії.
  • Розмірність і діапазони контрольовані; шукайте інваріанти для стиснення.
  • Перевірте базові випадки, порядок обчислення та можливість відновлення відповіді.

Коротка відповідь

Для співбесіди
Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Запропонувати правку