Алгоритмы с нуля
Dynamic programming: тест с множественным выбором
Суть Синтез по всему юниту dynamic programming: когда DP применима, memoization против tabulation, дизайн state, классические рекуррентности и их сложность.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов через весь юнит. Каждый отражает решение, которое вы принимаете в начале реальной DP-задачи — не определение для зубрёжки, а какое свойство проверить, какой state выбрать и какую сложность это даёт.
Цель
Убедитесь, что связываете два разрешающих свойства, два стиля реализации, дизайн state и классические рекуррентности — синтез, к которому вели отдельные уроки.
Викторина
Completed
Задача распадается на подзадачи, и вы подтвердили, что эти подзадачи повторяются. Достаточно ли этого, чтобы оправдать DP-решение?
Heads-up Overlapping subproblems оправдывают кэш, но DP нужны оба свойства. Без optimal substructure нет корректной рекуррентности для объединения подответов, и memoization просто быстро кэширует неверные ответы.
Heads-up Это описывает divide and conquer (например merge sort), а не DP. DP — это именно случай, когда subproblem ПЕРЕСЕКАЮТСЯ, из-за чего кэш и окупается.
Heads-up Если жадный выбор доказуемо работает, DP часто не нужна вовсе. DP — инструмент для случая, когда локальный жадный выбор проваливается, но optimal substructure всё же есть.
Викторина
Completed
У вас есть рабочее решение через memoization (сверху вниз). Когда переписывание его в tabulation (снизу вверх) стоит усилий?
Heads-up Обе вычисляют каждый отдельный state один раз, поэтому асимптотика одинакова. Tabulation выигрывает на константах, безопасности стека и оптимизации памяти, но не на big-O.
Heads-up Преимущество memoization на разрежённом множестве state реально, но не абсолютно: глубокая рекурсия переполняет стек, а хэш-кэш дороже массива на доступ. Это компромисс, а не правило.
Heads-up Базовые случаи есть у любой DP; это не связано. Tabulation именно требует порядка обхода, заполняющего ячейки до того, как их прочитают.
Викторина
Completed
Для House Robber рекуррентность dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Что кодирует каждая ветвь и почему хватает двух индексов истории?
Heads-up Наоборот. dp[i-1] — лучшее, когда дом i НЕ берут; dp[i-2]+nums[i] — лучшее, когда его БЕРУТ, ведь взятие i запрещает i-1.
Heads-up Ограничение соседства локально: взятие i запрещает только i-1. Поэтому dp[i] читает лишь dp[i-1] и dp[i-2], и две скользящие переменные заменяют весь массив.
Heads-up Грабёж через один проваливается на входах вроде [2,1,1,2]; оптимум берёт дома 0 и 3. Максимум по двум ветвям — именно то, чем DP бьёт жадное чередование.
Викторина
Completed
0/1 knapsack работает за O(n*W). Почему это называют псевдополиномиальным, а не полиномиальным?
Heads-up Версия с memoization или tabulation считает каждый state один раз — она не экспоненциальна по числу state. Псевдополиномиальность относится к зависимости от величины W, а не от ветвления.
Heads-up O(n*W) — это худший случай самой DP, а не средний. Цифра 2^n — это наивная рекурсия без memoization.
Heads-up Простота W неважна. Ярлык псевдополиномиальности целиком про то, что W — значение с логарифмической длиной записи.
Викторина
Completed
Алгоритм Longest Increasing Subsequence за O(n log n) хранит массив 'tails'. Что является ответом задачи и что на самом деле содержит массив tails?
Heads-up Tails — не реальная subsequence: каждая ячейка перезаписывается наименьшим хвостом для своей длины, и хранимые значения могут даже не идти в таком порядке во входе. Значима только его длина.
Heads-up Максимум — это просто наибольший размещённый элемент, он не связан с длиной LIS. Ответ — число занятых ячеек.
Heads-up Это массив O(n^2)-DP, а не tails. Массив tails индексируется по ДЛИНЕ subsequence, а не по позиции во входе, что и позволяет бинарный поиск.
Викторина
Completed
Interval DP (matrix chain, burst balloons) идёт по возрастанию длины интервала и выбирает точку разбиения k внутри [i..j]. Почему обходить по длине, а не привычно слева направо по i?
Heads-up Это требование корректности, а не стиль. Цикл по i слева направо доходит до dp[i][j] до заполнения dp[i+1][j-1] и читает мусор. Зависимость от более коротких интервалов значит, что длина должна быть внешним циклом.
Heads-up Базовый случай есть: интервалы длины 1 (или 0). Это и есть самые короткие интервалы, заполняемые первыми при обходе по длине.
Heads-up k пробегает все позиции внутри интервала; берут лучшее по всем разбиениям. Фиксация k серединой сломала бы оптимальность — оптимальное последнее действие редко в середине.
Итог
Сквозная линия юнита — один чеклист перед написанием любой DP: подтвердить overlapping subproblems И optimal substructure; спроектировать наименьший state, схватывающий решение (один индекс для House Robber, два для knapsack и LCS, интервал для matrix chain); выбрать memoization или tabulation по глубине стека и памяти, а не по big-O; и знать, что реально лежит в таблице — включая массив tails в LIS, ответом служит его длина, а не содержимое. Сложность одинакова: число state на работу на один state.