Dynamic programming

Dynamic programming применим, когда subproblems overlap и optimal answers строятся из smaller optimal answers. Сложность не в table, а в выборе state, который хранит все нужное и ничего лишнего. Memoization начинается с recursion, а tabulation заполняет states в dependency order.

На интервью: Интервьюеры ожидают recurrence, base cases, state dimensions, transition cost и итоговую complexity.

Типовые ошибки: Не форсируйте DP, когда greedy или sliding window достаточно. State explosions появляются, когда вы включаете raw history вместо compressed facts. Следите за modulo и reconstruction requirements.

Чеклист:

• Определите dp state.
• Запишите recurrence.
• Задайте base cases.
• Посчитайте dimensions times transition cost.