@eugrita

Является ли задача о размене суммы задачей динамического программирования?
Мне кажется нет. хотя это зависит от алгоритма решения.
Здесь обычно путают 2 задачи
1)задача нахождения количеств способов размена с учетом порядка купюр одинакового достоинства
да ,в этом случае алгоритм заключается в нахождении количества путей между начальной вершиной и нулевыми
или например в написании рекурсивных формул сведения к меньшей размерности например
S=30 f(30)=f(23)+f(27)+f(25) f(0)=1
f(23)=f(16)+f(20)+f(18) f(27)=f(20)+f(24)+f(22)
f(25)=f(18)+f(22)+f(20) и т д пока не доходят до 0 а потом обратно вверх

2)задача нахождения количества способов размена без учета порядка купюр одинакового достоинства
- здесь уже проходы по дереву не ведет к решению - надо считать одинаковыми все пути с одинаковым кол-вом купюр одних достоинств. (или делить на количество перестановок)

Я сам решаю данную задачу алгоритмом лексикографического перебора по комбинациям монет начиная от мах количества самых крупных купюр в сторону уменьшения. Это можно назвать задачей целочисленной оптимизации но никак по-моему динамическим программированием. Нет там ни рекурсивного обхода дерева, ни приема "c конца"
Правда для этой задачи в литературе иногда используют термин жадный алгоритм. Но я не виде подробного его описания

0

@Shamil1

Что это значит?

Да.

0