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

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

В динамическом программировании кажется, что все приводят в качестве первого примера задачу Фибоначчи и продолжают анализировать связанные понятия, такие как рекурсия и мемоизация.

Я считаю, что в таком подходе отсутствует ключевая идея DP: принцип оптимальности, также известный как оптимальная подструктура.

Говорят, что задача имеет оптимальную подструктуру, если ее решение вычислимо с использованием оптимального решения меньшей подзадачи.

Ричард Беллман (да, парень Беллман-Форд) в значительной степени изобрел динамическое программирование. Давайте послушаем его определение Принципа оптимальности:

«Оптимальная политика обладает тем свойством, что какими бы ни были начальное состояние и начальное решение, остальные решения должны представлять собой оптимальную политику в отношении состояния, полученного в результате первого решения».

Прочтите это еще раз, более внимательно. Он имеет высокую плотность концепций на слово, поэтому при первом чтении вы, вероятно, что-то упустили. Если вы полностью усвоите этот принцип, вы почти закончили с DP.

Вернемся к Фибоначчи. Этот Принцип Оптимальности полностью отсутствует, потому что определение Фибоначчи тонко структурировано. Это потому, что Фибоначчи — это даже не «задача»: это функция! Студента не побуждают к размышлению о классических шагах задачи ДП. Фальшивый пример, как назвал бы это кто-то в округе Колумбия.

Задача о рюкзаке — это пример, который уделяет принципу оптимальности должное внимание. Если вы хотите узнать больше: https://en.wikipedia.org/wiki/Knapsack_problem.

В заключение: авторы хорошо подбирают ваши примеры!