# Python Program to Print nth Fibonacci Number using Dynamic Programming with Memoization

This is a Python program to print nth Fibonacci number using dynamic programming with top-down approach or memoization.

Problem Description

Fibonacci numbers are defined by the sequence f(0) = 0, f(1) = 1 and f(n) = f(n – 1) + f(n – 2) for n >= 2. The program prompts the user to enter n and it prints the nth Fibonacci number.

Problem Solution

1. Two functions are defined, fibonacci and fibonacci_helper.
2. fibonacci_helper takes two arguments, a list r and a number n.
3. r[n] will contain the nth Fibonacci number.
4. fibonacci_helper fills the list r as it runs.
5. The function works by using the formula r[i] = r[i – 1] + r[i – 2] if i >= 2 and r[i] = i if i == 0 or i == 1.
6. The function is implemented recursively and as Fibonacci numbers are calculated they are stored in r.
7. If a Fibonacci number has been already calculated and stored in r, then it is immediately returned and not calculated again.
8. The function fibonacci takes a number n and returns the nth Fibonacci number.
9. It creates a list r and calls fibonacci_helper on n and r to get the nth Fibonacci number.

Program/Source Code

Here is the source code of a Python program to print the nth Fibonacci number using dynamic programming with memoization. The program output is shown below.

```def fibonacci(n):
"""Return the nth Fibonacci number."""
# r[i] will contain the ith Fibonacci number
r = [-1]*(n + 1)
return fibonacci_helper(n, r)

def fibonacci_helper(n, r):
"""Return the nth Fibonacci number and store the ith Fibonacci number in
r[i] for 0 <= i <= n."""
if r[n] >= 0:
return r[n]

if (n == 0 or n == 1):
q = n
else:
q = fibonacci_helper(n - 1, r) + fibonacci_helper(n - 2, r)
r[n] = q

return q

n = int(input('Enter n: '))

ans = fibonacci(n)
print('The nth Fibonacci number:', ans)```
Program Explanation

1. The user is prompted to enter n.
2. fibonacci is called to compute the nth Fibonacci number.
3. The result is then displayed.

Runtime Test Cases
```Case 1:
Enter n: 5
The nth Fibonacci number: 5

Case 2:
Enter n: 13
The nth Fibonacci number: 233

Case 3:
Enter n: 0
The nth Fibonacci number: 0```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

If you find any mistake above, kindly email to [email protected]