На эту неделю у нас практика к теории «Задача о монетах».

Это одна из самых базовых и важных тем в динамическом программировании: здесь хорошо видно, как формулируются состояния, как строятся переходы и как одна и та же идея может использоваться и для поиска оптимального ответа, и для подсчёта количества способов.

Теория:

• Задача о монетах — https://olprog.ru/articles/olprog/dp/coin-problem/

Практика к теме:

• Монеты для экспедиции — https://judje.olprog.ru/problem/expeditioncoins
• Чайная лавка мастера — https://judje.olprog.ru/problem/teablends
• Каменные плиты — https://judje.olprog.ru/problem/stoneplates
• Городские пропуска — https://judje.olprog.ru/problem/seasonpasses
• Склад жетонов — https://judje.olprog.ru/problem/warehousetokens

Эта подборка подойдёт тем, кто хочет не просто прочитать теорию, а сразу закрепить её на задачах. Во всех этих задачах полезно обращать внимание на одно и то же:

• что именно является состоянием динамики;
• как выразить ответ через более маленькие состояния;
• в каком порядке удобно считать значения;
• что именно хранить в массиве: минимум, количество способов или другой параметр.

Рекомендую идти именно в таком порядке: сначала внимательно прочитать теорию, затем попробовать самостоятельно выписать идею перехода для каждой задачи, и только после этого писать код. Такой подход помогает не просто решить конкретную задачу, а действительно почувствовать, как работает динамическое программирование.

Если в какой-то задаче не получается сразу увидеть решение — это нормально. На таких задачах как раз и формируется навык: выделять состояние, замечать повторяющиеся подзадачи и превращать рекурсивную идею в табличную динамику.

Удачи в решении!

Жду ваши результаты, вопросы и впечатления от задач.