Рекурсия: различия между версиями

Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы ''горками''. Пусть число a(i,j) есть число в треугольнике, находящееся в i-й строчке на j-м месте, а число (i,j) есть максимальное значение суммы, которое можно получить спускаясь с горки, начиная с этого элемента. Понятно, что (i,j) есть число a(i,j) плюс максимум из двух вариантов: (i+1,j) и (i+1,j+1). Эти два варианта соответствуют тому, что мы можем спуститься вниз-вправо или вниз-влево. Получилось рекурсивное определение: <math>S(i,j)=a(i,j)+\max(S(i+1,j),\;S(i+1, j+1)).</math> На основе этой рекуррентной формулы можно написать рекурсивный алгоритм. Но нужно быть осторожным. Попробуем вычислить время работы нашего алгоритма при входных данных максимального размера&nbsp;— 100 строк. Рекурсивный алгоритм вычисления функции <math>(.,.)</math> перебирает все возможные пути. Сколько их? На каждом шаге есть возможность выбрать один вариант из двух (направо или налево). Количество шагов равно количеству строк треугольника. Значит, количество всех путей равно <math>2^{Ref|1100}{</math>(Покажите, что число путей из вершины до j-го элемента i-й строчки равно биномиальному коэффициенту <math>C_i^j</math>.) <math>2^{100}</math>. Это очень большое число. Столько вариантов не успеет перебрать даже самая мощная вычислительная техника. Если предположить, что машина просматривает миллиард вариантов в секунду, то понадобится <math>2^{100} / 10^9</math> секунд. Чтобы считать было удобнее, заметим, что <math>2^{100} / 10^9 = 16^{25} / 10^9</math> > <math>10^{25} / 10^9 = 10^{16}</math>&nbsp;секунд, что соответствует более, чем <math>10^{12}</math> часов, или более <math>10\,000\,000</math>&nbsp;лет. Понятно, что такая программа никому не нужна, её результаты узнать невозможно. За такое время все компьютеры, решающие эту задачу, превратятся в пыль.

Решить эту задачу за разумное время помогает '''динамическое программирование'''. Суть динамического программирования хорошо описана в книге Р.&nbsp;Беллмана&nbsp;{{Ref|Bell}}. Есть и более современные учебники&nbsp;{{Ref|2}},{{Ref|3}}, в них можно найти много интересных алгоритмов, основанных на динамическом программировании.