Необходимо найти n-ый член последовательности , если: $F_{0}= 0$, $F_{1}= 1$, $F_{n}= F_{n-1}+ F_{n-2}$, где $n\geq2$, $n \in Z$

1. Подзадачей служит вычисление i-го числа Фибоначчи.

2. Рекуррентная формула для чисел Фибоначчи: $F_{n}= F_{n-1}+ F_{n-2}$
3. Начальными значениями для чисел Фибоначчи служат $F_{0}= 0$ и $F_{1}= 1$
4. Храниться числа будут в массиве, где в i-ой ячейке $F_{i}$:

5. Заполняя массив сначала, получается требуемый результат
6. n-й член Фибоначчи будет в n-й ячейке массива. Это и есть ответ

Псевдокод:

//arr - массив размерности (n+1), состоящий из членов последовательности

функция фибоначчи(n)
    arr <- [0, 1]
    для i от 2 до n
        arr[i] <- arr[i - 1] + arr[i - 2]
    вернуть arr[n]

#python

def fib_dp_back(n):
    if n < 0:
        return -1
    arr = [0, 1]
    for i in range(2, n + 1):
        q = arr[i - 1] + arr[i - 2]
        arr.append(q)
    return arr[n]

//C++
//sport version

int fib_dp_back(int n){
    if(n < 0){
        return -1;
    }
    int a[n + 1];
    a[0] = 0;
    a[1] = 1;
    for (int i = 2; i < n + 1; i++){
        a[i] = a[i - 1] + a[i - 2];
    }
    return a[n];
}  

//C++
//production version

template<typename ValueType>
ValueType fibonacci_dp_back(ValueType n){
    if(n < 0){
        return -1;
    }
    int arr[n + 1];
    arr[0] = 0;
    arr[1] = 1;
    for (int i = 2; i < n + 1; i++){
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n];
}