Ни одно интервью с техническими гигантами не проходит без вопроса от Dynamic Programming. Это своего рода причудливое название для запоминания или хранения значений для будущих ссылок.

Вам потребуется время, чтобы рассчитать Фибоначчи для 100?

Потребуется ли много времени, чтобы вычислить Фибоначчи для 100, скажем, вы знаете Фибоначчи для 98 и 99?

Что ж, если вам потребовалось время, чтобы ответить на последний вопрос, то эта статья не принесет вам никакой пользы (Пссс… подумайте о том, чтобы переделать математику в средней школе)

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

Для целых чисел это может быть решение для меньших целых чисел. Для строки это может быть решение для набора подстрок и т.д.

Чтобы продемонстрировать это, я хотел бы взять классический пример чисел Фибоначчи. Если вы хотите ознакомиться с рекурсивным решением или Фибоначчи, ознакомьтесь с: Итеративное решение Фибоначчи против рекурсивного.

Код С++:

Временная сложность:

Как мы видели в посте Итеративность Фибоначчи против рекурсии, рекурсивное решение занимает время O(2 ^ n).

Если мы посмотрим на дерево рекурсии, то по мере того, как рекурсивная функция проходит по самой длинной ветви дерева, все необходимые числа Фибоначчи вычисляются и сохраняются в массиве, поэтому дальнейшие обращения к этим значениям не порождают никаких новых деревьев и, следовательно, затраченное время указано ниже:

T(n) = T(n-1) + c
     = T(n-2) + 2c
     = T(n-3) + 3c
     = T(n-k) + kc
Let's find the value of k for which: n - k = 0
k = n
T(n) = T(0) + nc
     = nc + 1
i.e. time take by fibonacci recursive with memorization / Dynamic Programming is O(n).

Космическая сложность:

Сложность пространства для массива составляет O (n), а для стека рекурсивных вызовов также O (n). Следовательно, общая пространственная сложность равна O(n).

Зачем заходить так далеко, если мы можем итеративно найти решение чисел Фибоначчи за время O(n) и пространство O(1)?

Компромисс пространства с использованием динамического программирования позволяет нам вычислить предварительно рассчитанное значение за время O (1). Следовательно, в случае систем реального времени это может быть очень полезным и даже желательным.

Чтобы увидеть больше подобных сообщений, ознакомьтесь с моим другим контентом и подпишитесь на меня. Удачного кодирования !!