Объяснение
Динамическое программирование хранит решения повторяющихся подзадач. Состояние должно содержать всю информацию для перехода. Жадный выбор быстрее только там, где доказано, что локальное решение не ухудшает оптимум.
Задача для самостоятельного решения
Монеты 1, 3, 4: сколько монет нужно для суммы 6?
Показать разбор ответа
Жадно: 4+1+1, три монеты. Оптимум: 3+3, две. Формула dp[s]=1+min(dp[s−c]) по доступным c; dp[0]=0. Этот пример опровергает универсальность жадного подхода.