Основы ДП: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Рассмотрим такую задачу: найти N-е число Фибоначчи. Числа Фибоначчи определяются так: $F_0...») |
Глеб (обсуждение | вклад) |
||
Строка 36: | Строка 36: | ||
* обойти массив и заполнить ответы по формуле | * обойти массив и заполнить ответы по формуле | ||
* вывести ответ откуда-то из этого массива | * вывести ответ откуда-то из этого массива | ||
+ | |||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 20:12, 4 октября 2019
Рассмотрим такую задачу: найти 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$ (с помощью формулы)
- хранить все ответы в массиве
- заполнить начало массива вручную (для которых формула не работает)
- обойти массив и заполнить ответы по формуле
- вывести ответ откуда-то из этого массива
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin