ДП: числа Фибоначчи без пересчётов

Наивная рекурсия для чисел Фибоначчи пересчитывает одни и те же значения многократно. Напишите функцию fibonacci_dp(n), вычисляющую n-е число Фибоначчи (F(0)=0, F(1)=1) методом ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ (таблица снизу вверх, без повторных вычислений) за O(n).