Это Ричард Беллман, математик-прикладник, который ввел термин динамическое программирование в 1953 году. Этот термин несколько неверен, благодаря потоку HN я узнал, что это имя было выбрано Беллманом, чтобы устранить двусмысленность или путаницу в то время, поэтому что даже конгрессмен одобрил бы это.
Так что, если кого-то пугает это причудливое имя, не пугайтесь. Для всех практических целей динамическое программирование — это просто метод оптимизации. Это, безусловно, упрощение, но давайте начнем с этого. Нам легче укладывать в голове простые понятия.
Итак, что мы оптимизируем. При написании программного обеспечения обычно оптимизируются два типа операций:
Те, которым требуется доступ к диску, доступ к базе данных, сетевой ввод-вывод и т. д.
Те, которые алгоритмически неэффективны, используют несколько вложенных циклов и т. д.
Существует третий тип, который не очень очевиден и включает в себя операции, которые многократно вычисляют одно и то же значение. Подождите минутку, вы можете сказать, что это бред, ни один здравомыслящий человек так не делает. Я имею в виду, представьте, если вам нужно будет вычислить 4*3, а затем вычислить 5*4*3, а затем вычислить 6*5*4*3, что вы будете делать? Каким-то образом вы обнаружите, что повторяется 4*3, повторяется 5*4*3, поэтому нет необходимости вычислять их дважды. Конечно, накладные расходы на вычисление 4 * 3 дважды на современном компьютере практически ничтожны. Однако, когда эта постановка проблемы должна обобщаться... вы формулируете вышеуказанную проблему как
n * (n-1) * (n-2) …. 0
Это вводит функцию для вычисления 4 * 3 или n * (n - 1), и эти функциональные накладные расходы на повторное вычисление того же значения довольно высоки. Также не очень интуитивно понятно, когда вы смотрите на это уравнение, что есть возможности для оптимизации. То же уравнение переписано
n * (n-1) * (n-1–1) * (n-1–1–1) … 0
делает совершенно очевидным, как мы можем разделить семантику динамического программирования и лучше понять его с точки зрения простой оптимизации. Если вы заметили, в приведенном выше уравнении совершенно очевидно, что выполняется одна и та же операция, поэтому вы можете использовать одну и ту же функцию, просто вызывая ее повторно с простой оговоркой — не вызывайте функцию для значений, которые вы уже вычислили. . Сохраняйте эти значения и повторно используйте их по мере необходимости… что-то вроде «вызов функции, если результат не в кеше».
С этим я надеюсь, что любой, у кого есть трудности с пониманием динамического программирования, сможет приступить к работе. Я только начал царапать поверхность.
