Fibonacci D P Algorithm
The Fibonacci Dynamic Programming (DP) Algorithm is an efficient approach to solve the well-known Fibonacci series problem. The Fibonacci series is a sequence of numbers, where each number is the sum of the two preceding ones, usually starting with 0 and 1. The naive method of calculating Fibonacci numbers involves a recursive algorithm, which has an exponential time complexity of O(2^n) due to the repeated computation of overlapping subproblems. In contrast, the Fibonacci DP Algorithm utilizes memoization and bottom-up techniques to decrease the time complexity to O(n) by storing and reusing the results of previously computed subproblems, thus significantly improving the efficiency of the algorithm.
The core idea behind the Fibonacci DP Algorithm is to use an array or a hashmap to store the computed Fibonacci numbers, so they can be reused for future calculations. The algorithm starts by initializing the base cases, F(0) = 0 and F(1) = 1, and then iteratively computes the rest of the Fibonacci numbers using the formula F(n) = F(n-1) + F(n-2). The results are stored in the data structure to avoid redundant calculations, and the final result, F(n), is returned. The space complexity of this technique can be further optimized by only storing the last two Fibonacci numbers at each step, reducing the space complexity to O(1). The Fibonacci DP Algorithm is not only applicable to Fibonacci series problems but can be extended to other problems where overlapping subproblems exist, making it a powerful and versatile tool in computer programming and problem-solving.
//Fibonacci Series using Dynamic Programming
/* Author: Moinak Banerjee(moinak878)
Date : 1 October ,2019
*/
#include<stdio.h>
#include<stdlib.h>
int fib(int n)
{
//Out of Range checking
if(n<0){
printf("\nNo Such term !\n");
exit(0);
}
//declaring array to store fibonacci numbers -- memoization
int f[n+2]; // one extra to handle edge case, n = 0
int i;
/* let 0th and 1st number of the series be 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
// Adding the previous 2 terms to make the 3rd term
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main(){
int number;
//Asks for the number/position of term in Fibonnacci sequence
printf("Enter the value of n(n starts from 0 ): ");
scanf("%d", &number);
printf("The nth term is : %d \n", fib(number));
return 0;
}