Алгоритмы с нуля
Динамическое программирование: тренажёр для собеседований
Memoization и tabulation ты понимаешь. Собеседование проверяет, заметишь ли ты перекрывающуюся подзадачу под таймером, запишешь ли рекуррентное соотношение и объяснишь ли вслух, почему оно верно.
Реши каждую задачу до того, как откроешь подсказку, уложись в целевое время и проговаривай временную и пространственную сложность так, будто тебя слушает интервьюер. Подсказки нужны, когда ты по-настоящему застрял — они подталкивают к приёму, но не выдают всё решение.
Шесть задач из NeetCode-150 на приёмы одномерного и двумерного DP из этого раздела. Засеки время, реши каждую вхолодную без подсказок, затем проговори вслух временную и пространственную сложность, прежде чем двигаться дальше. Открывай подсказку, только если действительно застрял — подсказки подталкивают, но не выдают ответ.
0/6 решено
1d dp
Follow-up (вслух)
Ты читаешь только два последних состояния. Проговори, как это сжимает память с O(n) до O(1).
Follow-up (вслух)
В чём здесь аргумент об оптимальной подструктуре — почему лучший ответ для префикса зависит только от двух предыдущих ответов?
Follow-up (вслух)
Назови временную и пространственную сложность через сумму и число монет. Почему жадность проваливается, а DP нет?
Follow-up (вслух)
В версии O(n log n) длина массива tails — это ответ, но его содержимое не является настоящей подпоследовательностью. Почему это всё равно верно?
2d dp
Follow-up (вслух)
Назови временную и пространственную сложность для строк длины m и n, затем объясни, как снизить память до O(min(m,n)).
Follow-up (вслух)
Есть и чисто комбинаторный ответ: C(m+n-2, m-1). Почему сеточный DP равен этому биномиальному коэффициенту и что бы ты написал на собеседовании?
Отмечай задачу решённой, только когда сделал её вхолодную, уложился в целевое время и смог назвать рекуррентное соотношение и сложность без запинки. Вернись через несколько дней и перерешай отмеченные — именно интервальные повторы превращают узнанный приём в рефлекс.