Python dynamic programming
Fibonacci numbers satisfy F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2). Naive recursion repeats the same subproblems many times.
Python
def fibonacci(n):
if n < 0:
raise ValueError("n must be nonnegative")
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fibonacci(6))
assert fibonacci(0) == 0
assert fibonacci(1) == 1