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

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

Для нахождения $i-го$ числа Фибоначчи понадобятся только $i-1$ и $i-2$

Псевдокод:

//a и b - два последних известных члена последовательности
//c - следующий за a и b член последовательности

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

#python

def fib_ec_mem(n, a = 0, b = 1):
    if n < 0:
        return -1
    if n == 0:
        return a
    else:
        return fib_ec_mem(n - 1, b, a + b)

//C++
//sport version
  
int fib_ec_mem(int n){
    if(n < 0){
        return -1;
    }
    int a = 1;
    int b = 0;
    int c;
    for (int i = 1; i < n + 1; i++){
        c = a + b;
        int a1, b1;
        a1 = b;
        b1 = c;
        a = a1;
        b = b1;
    }
    return b;
}  

//C++
//production version

template<typename ValueType>
ValueType fibonacci_economy_memory(ValueType n){
    if(n < 0)
        return -1;
    ValueType a = 1;
    ValueType b = 0;
    ValueType c;
    for (int i = 1; i < n + 1; i++){
        c = a + b;
        ValueType a1, b1;
        a1 = b;
        b1 = c;
        a = a1;
        b = b1;
    }
    return b;
} 

Принцип работы на графах:

Так выглядит граф чисел Фибоначчи, eсли решать через рекурсию. Одни и те же элементы ищутся заново.

Так выглядит "хитрый" граф решения через ДП. Каждый элемент высчитывается ровно один раз, что помогает сэкономить как память, так и время.