Основы ДП
Рассмотрим такую задачу: найти N-е число Фибоначчи.
Числа Фибоначчи определяются так: $F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1}$.
Эту задачу можно решить рекурсивно:
1 void fibonacchi(int n) {
2 if (n == 0) {
3 return 0;
4 }
5 if (n == 1) {
6 return 1;
7 }
8 return fibonacchi(n - 2) + fibonacchi(n - 1);
9 }
Однако это будет работать долго. 20-е число посчитать еще можно будет, а 40-е число - нет. И не потому, что числа большие. А потому, что мы будем делать слишком много лишней работы. Число операций будет экспоненциально относительно $N$. Почему? Потому что, чтобы посчитать N-е число, нам нужно будет независимо посчитать (N-1)-е число и (N-2)-е число, и это в минимум в два раза больше действий, чем нужно для (N-2). А значит, для подсчета N-го числа Фибоначчи необходимо 2 раза посчитать (N-2)-е число, и это занимает в два раза больше времени, а значит это хотя бы $2^\frac{N}{2}$ действий. Это очень долго и главное, что это легко исправляется. Давайте просто не считать лишних действий - если мы один раз посчитали $F_k$, то давайте запомним, чему оно равно, и в следующий раз, когда оно нам понадобится, мы используем его сразу. Удобнее всего сохранить числа Фибоначчи прямо в массиве:
1 int fib[N];
2 fib[0] = fib[1] = 1;
3 for (int i = 2; i < N; i++) {
4 fib[i] = fib[i - 2] + fib[i - 1];
5 }
Это и называется динамическим программированием (или динамикой, ДП). Основная идея состоит в том, чтобы
- свести задачу для $N$ к задаче для чисел, меньших, чем $N$ (с помощью формулы)
- хранить все ответы в массиве
- заполнить начало массива вручную (для которых формула не работает)
- обойти массив и заполнить ответы по формуле
- вывести ответ откуда-то из этого массива