Top-down dynamic programming
Published: 2023-11-25 22:23:03


Динамическое программирование это способ решения алгоритмической задачи путем ее разбиения на подзадачи. Классический пример — это числа Фибоначчи. Задача нахождения n числа Фибоначчи формулируется через числа Фибоначчи n-1 и n-2. Fn = Fn-1 + Fn-2.

Есть два подхода в динамическом программировании:

 1. **Top-down**. Рекурсивное с мемоизацией (используем кэш, чтобы не решать уже решенные подзадачи несколько раз). Например, рекурсивное решение для задачи про числа Фибоначчи. f(n) = f (n — 1) + f (n-2).

 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 способ.

Напишем это в виде кода:

```java
    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 ступенек:

![](https://cdn-images-1.medium.com/max/7132/1*8GbQv7aZZ_9tNDNOoL6k7Q.png)

Добавим результаты всех вызовов:

![](https://cdn-images-1.medium.com/max/7132/1*0t1LBOFmlAQPsYOGOT720w.png)

Можно заметить, что мы делам одни и теже вызовы множество раз. Например, f(1) 7 раз, f(2) 5 раз, f(3) 2 раза.

Я отметил базовые случаи зеленым, а повторяющиеся случаи одинаковыми цветами:

![](https://cdn-images-1.medium.com/max/7132/1*XvtU5_8FKGNo6oSW3zXa6A.png)

Мы может ускорить работу нашего решения если будем кэшировать результаты прошлых вычислений и их переиспользовать при последующий вызовах. Это называется **мемоизацией** (**memoization**).

Код, в котором мы используем такой кэш:

```java
    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;
    }
```

Тогда количество вызовов нашей функции сократиться. Я отметил черным цветом случаи, когда мы просто вернем результат из кэша.

![](https://cdn-images-1.medium.com/max/6566/1*vdp2kRuwANF0PCsf8wHahg.png)