Dynamic programming: тест со свободным воспроизведением
Подсказки на свободное воспроизведение по всему юниту DP. Сначала ответьте своими словами, затем раскройте образцовый ответ и сравните.
Воспроизведение бьёт перечитывание. На каждую подсказку проговорите или запишите полный ответ по памяти, прежде чем открыть образец — именно усилие припоминания закрепляет материал.
Восстановите хребет юнита — два разрешающих свойства, memoization против tabulation, как спроектировать state и его transition, и как работает оптимизация памяти — не подсматривая в уроки.
- 01Какие два свойства должна иметь задача, прежде чем применима dynamic programming, и что даёт каждое?
- 02Сравните memoization и tabulation. Когда выбрать каждое?
- 03Как спроектировать state для DP-задачи и что делает state корректным?
- 04Что такое transition и почему порядок обхода должен его уважать?
- 05Объясните, как работает оптимизация памяти (скользящий массив) и когда она безопасна.
- 06Возьмите Longest Increasing Subsequence: дайте O(n^2) DP, идею O(n log n) и ловушку быстрой версии.
Если вы смогли восстановить каждый ответ по памяти, вы держите хребет юнита: подтвердить overlapping subproblems и optimal substructure, выбрать memoization или tabulation по глубине стека и памяти (а не по big-O), спроектировать минимальный достаточный state, написать transition по каждому выбору и обходить в порядке, уважающем его, и свернуть таблицу в окно лишь когда ни одно ещё нужное значение не перезаписывается. Сложность одинакова — число state на работу на один state.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.