Динамическое программирование это способ решения алгоритмической задачи путем ее разбиения на подзадачи. Классический пример — это числа Фибоначчи. Задача нахождения n числа Фибоначчи формулируется через числа Фибоначчи n-1 и n-2. Fn = Fn-1 + Fn-2.
Есть два подхода в динамическом программировании:
Top-down. Рекурсивное с мемоизацией (используем кэш, чтобы не решать уже решенные подзадачи несколько раз). Например, рекурсивное решение для задачи про числа Фибоначчи. f(n) = f (n — 1) + f (n-2).
Bottom-up. Сначала решаем подзадачи и постепенно идем к общей задачи. Итеративное решение, в котором мы храним уже вычисленные результаты. Обычно это одномерный или многомерный массив. Для чисел Фибоначчи это последовательное итеративное вычисление всех чисел Фибоначчи начиная с первого и сохранением промежуточных значений в переменных или массиве.
Рассмотрим Top-Down подход более детально на примере.
Задача. Человек идет по лестнице, в которой n ступенек. На каждом шаге, человек может перейти на следующую ступеньку, или перешагнуть одну или две ступеньки. Нужно найти число способов, которыми человек может преодолеть лестницу.
Например, для 3 ступенек есть 4 способа:
1+1+1 (по одной ступеньке за шаг),
1+2 (первый шаг — одна ступенька, второй перешагнуть через одну ступеньку),
2+1 (первый шаг через одну ступеньку, второй на следующую ступеньку),
3 (сразу на последнюю ступеньку).
Решение. В этой статье рассмотрим Top-Down решение.
Для этого нужно решение задачи для n ступенек представить рекурсивно, через решения подзадач с меньшим числом ступенек.
В данном случае, на каждом шаге у нас есть разветвление: шагнуть на одну ступеньку, шагнуть на две ступеньки, шагнуть на три ступеньки.
Пусть решение для n ступенек это f(n) (число способов преодолеть n ступенек), тогда можно составить рекурсивное выражение используя это разветвление:
f(n) = f(n-1) + f(n-2) + f(n-3).
Т.е. число способов преодолеть n-ступенек равно *сумме *числа способов преодолеть n-1 ступенек (после того как мы шагнули на 1 ступеньку), числа способов преодолеть n-2 ступенек (после того как мы шагнули на 2 ступеньки) и числа способов преодолеть n-3 ступеньки (после того как мы шагнули на 3 ступеньки).
После того, как мы составили рекурсивное выражение, нам нужно определить base-case (базовые случаи). Когда мы будем делать рекурсивные вызовы, мы должны в какой-то момент остановиться.
В данном случае, если число ступенек стало отрицательным, то результат будет 0. Это значит, что этот способ не валиден. Например, у нас 2 ступеньки и мы шагнули на 3. У нас осталось минус 1 ступенька. Такой вариант будем считать не валидным и результат — 0 способов.
Второй базовый случай — когда число ступенек стало равно нулю. В таком случае результат 1. Например, у нас было 2 ступеньки, мы шагнули на 1, осталась 1. Потом еще шагнули на 1. Осталось 0 ступенек. Это означает что мы достигли вершины лестницы и такой вариант ее прохождения валиден. Поэтому результат 1 способ.
Напишем это в виде кода:
int countWays(int n) {
if (n < 0) {
return 0;
}
if (n == 0) {
return 1;
}
return countWays(n - 1) + countWays(n - 2) + countWays(n - 3);
}
Т.к. на каждом шаге есть разветвление на 3 подветки, то общее число рекурсивных вызовов будет 3^n. Поэтому алгоритмическая сложность такого решения O(3^n).
Давайте отобразим дерево вызовов нашей функции для случая 5 ступенек:
Добавим результаты всех вызовов:
Можно заметить, что мы делам одни и теже вызовы множество раз. Например, f(1) 7 раз, f(2) 5 раз, f(3) 2 раза.
Я отметил базовые случаи зеленым, а повторяющиеся случаи одинаковыми цветами:
Мы может ускорить работу нашего решения если будем кэшировать результаты прошлых вычислений и их переиспользовать при последующий вызовах. Это называется мемоизацией (memoization).
Код, в котором мы используем такой кэш:
int countWays(int n) {
Map<Integer, Integer> cache = new HashMap<>();
return countWays(n, cache);
}
int countWays(int n, Map<Integer, Integer> cache) {
if (n < 0) {
return 0;
}
if (n == 0) {
return 1;
}
//есть ли такое значение к кэше, если есть,
//то возвращаем закэшированное значение
if (cache.containsKey(n)) {
return cache.get(n);
}
int result = countWays(n - 1, cache)
+ countWays(n - 2, cache)
+ countWays(n - 3, cache);
//сохраняем вычисленный результат в кэше
cache.put(n, result);
return result;
}
Тогда количество вызовов нашей функции сократиться. Я отметил черным цветом случаи, когда мы просто вернем результат из кэша.
Top comments (0)