Представьте себе: вы стоите у подножия лестницы, которая ведёт аж на сотую ступеньку. Задача — выяснить, сколько способов существует добраться до вершины, если за один шаг можно прыгать либо на одну, либо на две ступени. Звучит как начало эпической саги или испытание для героя компьютерной игры, правда? Но отвечать сразу — всё равно что пытаться угадать вес слона по фотографии носа.
Тут нужна стратегия!
И вот тут на сцену выходит наш герой — динамическое программирование. Не пугайтесь страшного слова! На самом деле это просто способ умно решать сложные задачи, разбивая их на мелкие и понятные кусочки.
Представьте, что вам нужно съесть огромный торт (ну или хотя бы попробовать). Вы же не проглотите его целиком за раз? Правильно — сначала откусите маленький кусочек, потом ещё один… И так постепенно доберётесь до последнего ломтика.
Вот и динамическое программирование работает примерно так же: сначала считаем для первой ступеньки, потом второй, третьей… и так далее.
К слову, слово «программирование» в названии этого метода появилось задолго до того, как появились компьютеры с их бесконечными обновлениями и мемами про баги. В 1950 году американский математик Ричард Беллман придумал этот метод для оптимизации сложных процессов. Тогда «программирование» означало не написание кода в Python или JavaScript, а… составление плана действий!
Так что если ваш дедушка говорит «я программист», вспоминая свою молодость — возможно, он имел в виду именно это.
Теперь представьте себе задачу: сколько способов превратить число 1 в число 100 с помощью операций «прибавить 3» и «умножить на 2»? Сразу ответить сложно — это как попытаться угадать все ингредиенты блюда после одного укуса пирога бабушки. Но если считать количество способов для промежуточных чисел (скажем, для 2, для 4), то постепенно можно дойти и до ответа для 100.
А теперь внимание: ключевое слово — рекуррентное соотношение! Если вы услышите этот термин на вечеринке — не пугайтесь!
Это просто формула, которая позволяет выразить решение большой задачи через решения её более маленьких частей. Представьте башню из кубиков: чтобы узнать высоту башни из десяти кубиков, достаточно знать высоту башни из девяти кубиков и добавить один кубик сверху. Вот вам и рекуррентное соотношение: H(10) = H(9) + h.
Но если вы думаете, что всё так просто всегда — вспомните числа Фибоначчи!
Эти ребята устроены хитрее: каждое число равно сумме двух предыдущих. F(n) = F(n-1) + F(n-2). А базовые случаи здесь — F(0) = 0 и F(1) = 1.
Ах да!
Кто такой этот Фибоначчи? Леонардо Пизанский был средневековым математиком XIII века (да-да, тот самый парень с итальянским акцентом), который решил посчитать кроликов. Не спрашивайте почему именно кроликов!
Видимо у него была ферма или он просто любил математику настолько сильно, что даже размножение пушистых зверьков стало поводом для исследований. Он выяснил: если каждая пара кроликов ежемесячно рождает новую пару после второго месяца жизни своих детей — то количество пар кроликов растёт по последовательности 0, 1, 1, 2, 3… и так далее.