Карточка Middle Динамическое программирование обновлено
Как составить DP
Вопрос
Из каких шагов состоит решение задачи динамикой?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
1) Состояние: что значит dp[i] (или dp[i][j]). 2) Переход: как dp[i] выражается через меньшие.
Ответ
- Состояние: что значит dp[i] (или dp[i][j]). 2) Переход: как dp[i] выражается через меньшие. 3) База: известные значения. 4) Порядок вычисления. 5) Где ответ. Потом оптимизация памяти, если хватает последних строк.
Разбор
- Состояние: что значит dp[i] (или dp[i][j]). 2) Переход: как dp[i] выражается через меньшие. 3) База: известные значения. 4) Порядок вычисления. 5) Где ответ. Потом оптимизация памяти, если хватает последних строк.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.