Модуль: Динамическое программирование. Основы

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

Задача

Предположим, нам нужно вычислить 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-ым числом Фибоначчи.
 

# Инициализация базовых случаев
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"

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