Top-down dynamic programming

Динамическое программирование это способ решения алгоритмической задачи путем ее разбиения на подзадачи. Классический пример — это числа Фибоначчи. Задача нахождения 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 способ.

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

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

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