Python Program to Print nth Fibonacci Number using Dynamic Programming with Bottom-Up Approach

This is a Python program to print nth Fibonacci number using dynamic programming with bottom-up approach.

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. The function fibonacci is defined.
2. fibonacci takes a number n and returns the nth Fibonacci number.
3. It creates a list r where r[n] will contain the nth Fibonacci number.
4. r[0] and r[1] are first initialized to 0 and 1 respectively.
5. The function then fills r by using the formula r[i] = r[i – 1] + r[i – 2].
6. The nth Fibonacci number is then returned.

Program/Source Code

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

def fibonacci(n):
    """Return the nth Fibonacci number."""
    if n == 0:
        return 0
    # r[i] will contain the ith Fibonacci number
    r = [-1]*(n + 1)
    r[0] = 0
    r[1] = 1
    for i in range(2, n + 1):
        r[i] = r[i - 1] + r[i - 2]
    return r[n]
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: 7
The nth Fibonacci number: 13
Case 2:
Enter n: 1
The nth Fibonacci number: 1
Case 3:
Enter n: 3
The nth Fibonacci number: 2

Sanfoundry Global Education & Learning Series – Python Programs.

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

Note: Join free Sanfoundry classes at Telegram or Youtube

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

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.