Динамическое программирование. Основы


Динамическое программирование

Рассмотрим рекурсивное решение задачи про последовательность чисел Фибоначчи.
 
C++ 
int fibonacci(int n) 
{
    if (n <= 0) 
    {
        return 0;
    } 
    else if (n == 1) 
    {
        return 1;
    } 
    else 
    {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
 
Python 
def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


Данная реализация функции fibonacci  работает, но имеет недостатки, связанные с экспоненциальной сложностью и дублированием вычислений.

Для более эффективного решения задачи о числах Фибоначчи, лучше использовать мемоизацию или динамическое программирование, чтобы избежать повторных вычислений и снизить сложность алгоритма до линейной (O(n)).

 
Динамическое программирование (DP) - это метод решения сложных задач, который состоит в разбиении задачи на более мелкие подзадачи и решении их, а затем комбинировании результатов для получения решения исходной задачи. DP широко применяется в информатике, математике, экономике и других областях для оптимизации и поиска оптимальных решений.


В динамическом программировании (DP) существует два основных метода решения задач: сверху вниз (Top-Down) и снизу вверх (Bottom-Up).  Каждый из них имеет свои преимущества и подходит для разных типов задач. Эти два метода можно использовать для решения широкого спектра задач, включая вычисление оптимальных путей, нахождение максимальных или минимальных значений, управление ресурсами и др. Выбор метода зависит от конкретной задачи, структуры данных и потребностей в оптимизации производительности.
 

Метод сверху-вниз

Метод сверху вниз (Top-Down) в динамическом программировании (ДП) - это подход, который начинает решать задачу с самых больших, общих исходных данных и разбивает ее на более мелкие подзадачи. Затем он решает каждую подзадачу рекурсивно, используя мемоизацию (запоминание результатов решения подзадач) для избегания повторных вычислений. Этот метод также называется "методом с кэшированием" или "методом с сохранением результатов".

Основные шаги метода сверху вниз в ДП:

  1. Определение базовых случаев: Определите базовые случаи, которые можно легко решить без дополнительных вычислений. Эти случаи будут останавливать рекурсивные вызовы.

  2. Рекурсивное разбиение задачи: Разбейте основную задачу на более мелкие подзадачи, которые можно решить рекурсивно. Обычно это делается путем выделения параметра, который будет уменьшаться с каждым рекурсивным вызовом.

  3. Использование мемоизации: Для каждой подзадачи сохраняйте результат ее решения в памяти (например, в массиве или словаре), чтобы избежать повторных вычислений при повторных вызовах.

  4. Сбор результатов: Верните результат решения основной задачи, используя результаты решенных подзадач.

Метод сверху вниз позволяет эффективно решать задачи, которые имеют перекрывающиеся подзадачи, и снижать сложность алгоритма до более оптимальной, чем при обычной рекурсии.


Метод сверху вниз с мемоизацией помогает избегать повторных вычислений и значительно улучшает производительность алгоритма, особенно для задач с большими входными данными. 

Использование данного метода для решения задачи про числа Фибоначчи расcмотрено в практическом примере. 

Задача для тренировки:

Числа Фибоначчи: Мемоизация рекурсии (C++)

Основная теория описана в задаче Числа Фибоначчи: Мемоизация рекурсии (C++)

Задача для тренировки:

Числа Фибоначчи: Мемоизация рекурсии (Python)

Динамическое программирование. Метод "снизу-вверх"

Метод "снизу вверх" (Bottom-Up) в динамическом программировании - это стратегия решения задач, которая начинается с решения наименьших подзадач и постепенно комбинирует их результаты для решения более крупной задачи. Этот метод избегает рекурсии и обычно использует циклы для эффективной обработки задачи.


Задача

Предположим, нам нужно вычислить n-ое число Фибоначчи, где n - это положительное целое число.

  1. Инициализация: Создадим массив для хранения результатов вычислений (назовем его fib) и установим начальные значения для чисел Фибоначчи: fib[0] = 0 и fib[1] = 1.

  2. Итерация: Начнем цикл с i = 2 и продолжим до i = n. На каждой итерации мы будем вычислять fib[i] на основе fib[i-1] и fib[i-2]:

    for i from 2 to n: fib[i] = fib[i-1] + fib[i-2]

  3. Результат: По завершении цикла fib[n] будет содержать n-ое число Фибоначчи.

Метод снизу вверх эффективен, так как избегает дублирования вычислений и имеет линейную сложность по времени. Вычисления производятся с самой маленькой подзадачи, решение которой сохраняется в массиве. Для решение более крупных подзадач используются решения более мелких подзадач.

Например, для n = 6, вычисление будет следующим образом:

  • fib[2] = fib[1] + fib[0] = 1 + 0 = 1
  • fib[3] = fib[2] + fib[1] = 1 + 1 = 2
  • fib[4] = fib[3] + fib[2] = 2 + 1 = 3
  • fib[5] = fib[4] + fib[3] = 3 + 2 = 5
  • fib[6] = fib[5] + fib[4] = 5 + 3 = 8

Таким образом, fib[6] равно 8, что является 6-ым числом Фибоначчи.
 

Python 
# Инициализация базовых случаев
fib = [0, 1]  # Первые два числа Фибоначчи

n = 10  # Найти 10-е число Фибоначчи

# Вычисление остальных чисел Фибоначчи "снизу вверх"
for i in range(2, n + 1):
    next_fib = fib[i - 1] + fib[i - 2]
    fib.append(next_fib)

# Результат
print(f"Fib({n}) = {fib[n]}")  # Выводит "Fib(10) = 55"



 

C++ 
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> fib(2);  // Инициализация базовых случаев
    fib[0] = 0;
    fib[1] = 1;

    int n = 10;  // Найти 10-е число Фибоначчи

    // Вычисление остальных чисел Фибоначчи "снизу вверх"
    for (int i = 2; i <= n; i++) {
        int next_fib = fib[i - 1] + fib[i - 2];
        fib.push_back(next_fib);
    }

    // Вывод результата
    cout << "Fib(" << n << ") = " << fib[n] << endl;  
    
    // результат "Fib(10) = 55"
    return 0;
}

 

Задача для тренировки:

Числа Фибоначчи. Динамика снизу вверх