Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Чому важливо правильно обрати стан у динамічному програмуванні?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)- Стан визначає, які підзадачі ви розв'язуєте і як повторно використовуються їхні результати. - Правильний стан забезпечує коректність (немає пропусків і подвійного підрахунку) та прозорі переходи. - Від нього напряму залежать асимптотика за часом/пам'яттю та можливість оптимізацій (стиснення вимірів, монотонності). - Неправильний стан часто призводить до експоненти, складних або некоректних переходів і неможливості відновити відповідь.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь - Стан визначає, які підзадачі ви розв'язуєте і як повторно використовуються їхні результати. - Правильний стан забезпечує коректність (немає пропусків і подвійного підрахунку) та прозорі переходи. - Від нього напряму залежать асимптотика за часом/пам'яттю та можливість оптимізацій (стиснення вимірів, монотонності). - Неправильний стан часто призводить до експоненти, складних або некоректних переходів і неможливості відновити відповідь. ## Розгорнута відповідь ### Що таке стан у ДП Стан - це мінімальний набір параметрів, який однозначно описує підзадачу так, щоб її розв'язок можна було повторно використати. У таблиці/кеші ми зберігаємо цільову метрику (мінімум, максимум, кількість, булеве значення досяжності) для цього набору параметрів. ### Чому вибір стану критичний - Коректність: стан повинен містити рівно ту інформацію, яка впливає на майбутні рішення. Недостатній - веде до пропуску валідних рішень; надлишковий - до подвійного підрахунку і зайвих вимірів. - Прості переходи: добре обраний стан дає локальні й детерміновані переходи. Поганий - змушує «озиратися назад» далеко або перебирати історію. - Складність: розмірність і діапазони параметрів стану визначають розмір таблиці ДП і кількість переходів (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). ### Типові помилки під час вибору стану - Недостатній стан: не зберігає ключовий фактор (останній елемент, залишковий ресурс, баланс). Підсумок - некоректні або експоненційні переходи. - Надлишковий стан: додано параметри, які не впливають на майбутнє рішення (зайва історія), що роздмухує таблицю і час. - Неправильний порядок обходу: стан обрано вірно, але обчислюється до того, як готові всі залежності. - Відсутність інваріантів: метрика в стані не підтримує монотонності/мінімальності, що позбавляє оптимізацій. ### Коротка пам'ятка - Стан = мінімальний контекст, що впливає на наступний крок. - Переходи локальні і не потребують додаткової історії. - Розмірність і діапазони контрольовані; шукайте інваріанти для стиснення. - Перевірте базові випадки, порядок обчислення та можливість відновлення відповіді.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.