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

1. Значение в i-й ячейке считается идеальным. Заполнение массива с числами Фибоначчи будет происходить сначала
2. Текущее значение для последующих членов последовательности используется по формулам: $F_{i - 1} = F_{i - 1} + F_{i}$, $F_{i - 2} = F_{i - 2} + F_{i}$

Псевдокод:

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

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

#python

def fib_dp_forward(n):
    if n < 0:
        return -1
    arr = [0, 1] + [0] * n
    for i in range(0, n):
        arr[i + 1] += arr[i]
        arr[i + 2] += arr[i]
    return arr[n]

//C++
//sport version

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

//C++
//production version

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