Полное руководство по DP с подробными примерами и диаграммами.
Возможно, вы слышали или в настоящее время изучаете динамическое программирование.
Вы прошли через множество руководств, в которых перечислено множество понятий и формул, от которых у вас кружится голова, но вы все еще не можете понять динамическое программирование.
Динамическое программирование кажется очень сложным и трудным для изучения алгоритмом.
На самом деле это не так. Динамическое программирование — очень оригинальный и логичный алгоритм. Если вы понимаете его принципы, вы можете досконально освоить этот алгоритм.
Здесь я надеюсь использовать простой английский язык, диаграммы и тематические исследования, чтобы заново изобрести динамическое программирование вместе с вами.
Оплата банкнотами.
Во-первых, давайте рассмотрим проблему, с которой мы часто сталкиваемся в реальной жизни.
Предположим, у нас есть много банкнот, и их номиналы:
- 1
- 5
- 10
- 20
- 50
- 100
Я считаю, что номиналы банкнот в большинстве стран должны быть такими.
Теперь мы покупаем определенный продукт, который стоит x долларов. Наша цель — использовать эти банкноты для оплаты точной суммы x долларов и, если возможно, использовать как можно меньше банкнот. Собственно, это соответствует нашим повседневным привычкам. Когда мы расплачиваемся наличными в реальной жизни, мы обычно надеемся использовать как можно меньше купюр.
Предполагая, что цена продукта сейчас составляет 777 долларов, какое минимальное количество номиналов нам нужно использовать?
Хм, прямо сейчас, не рассматривая никакой алгоритмической теории, вспомните свой жизненный опыт (только не говорите мне, что вы никогда не использовали банкноты для покупки товаров, ха-ха). Мы, очевидно, можем принять эту стратегию:
