Основы ДП: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Рассмотрим такую задачу: найти 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