Fibonacci sequence using Dynamic programming
- Padmasree
- October 7, 2020
- 11:05 am
- No Comments
Welcome to Python for fun! Here is the code to find the Fibonacci sequence using dynamic programming.
Fibonacci sequence is a series of numbers formed by the addition of the preceding two numbers in the series.
Dynamic programming is breaking down a problem into smaller sub-problems, solving each sub-problem, and storing the solutions to each of these sub-problems in an array (or similar data structure) so each sub-problem is only calculated once.
Example of Fibonacci Series: 0,1,1,2,3,5
In the above example, 0 and 1 are the first two terms of the series. These two terms are printed directly. The third term is calculated by adding the first two terms. In this case 0 and 1. So, we get 0+1=1. Hence 1 is printed as the third term. The next term is generated by using the second and third terms and not using the first term. It is done until the number of terms you want or requested by the user. In the above example, we have used five terms.
Note: Loved this Post? You too can publish your article on Python for fun which will be loved by millions. Contribute an Article!
def fibonacci(num):
arr = [0,1]
print("Dynamic Approach: ",end= ' ')
if num==1:
print('0')
elif num==2:
print('[0,','1]')
else:
while(len(arr)<num):
arr.append(0)
if(num==0 or num==1):
return 1
else:
arr[0]=0
arr[1]=1
for i in range(2,num):
arr[i]=arr[i-1]+arr[i-2]
print(arr)
return arr[num-2]
fibonacci(10)
