#### Dynamic Programming

**Problem **

Find the **n**^{th} term of fibonacci series.

**Solution **

In a **Fibonacci** series, every term is equal to the sum of previous two terms :

**0 , 1 , 1 , 2 , 3 , 5 , 8 ,13 , 21 , 34 , 55 , …..**

Mathematically, **fib ( n ) = fib ( n – 1 ) + fib ( n – 2 )** with **fib ( 0 ) = 0** and **fib ( 1 ) = 1**. This is the structure of an optimal solution defined recursively.

Recursive function to find the **n**^{th} term is show below. This is not an efficient solution since there will be repeated computation for some sub-problems. Dynamic programming approach maintains an array **fib** of size **n + 1** in which each fibonacci term starting from **0 ^{th}** term is stored. For e.g,

**fib [ 2 ]**stores the

**2**

^{nd}term of fibonacci series. Finally,

**fib [ n ]**gives the

**n**term.

^{th}See the function

**getFibTerm2 ( int n )**below for the dynamic programming solution.

#include<iostream> using namespace std; // recursive function to get the nth term of fibonacci series // not an efficient implementation // will become extremely slow for large values of n // Fib(n) = Fib(n-1) + Fib(n-2) int getFibTerm1(int n) { if (n < 0) return -1; // invalid input if (n == 0 || n == 1) return n; // boundary cases return getFibTerm1(n-1) + getFibTerm1(n-2); } // Dynamic programming solution // Very efficient in terms of time complexity int getFibTerm2(int n) { // array to store the value of each term of series till n. // Dynamic programming is all about storing the computed values // so that we need not compute it again during further processing int fib[n+1]; fib[0] = 0; fib[1] = 1; int i; for (i=2;i<=n;i++) { fib[i] = fib[i-1]+fib[i-2]; } return fib[n]; } // main int main() { int n = 6; int nth_fib_term = getFibTerm2(n); cout<<"Fib term :: "<<nth_fib_term; cout<<endl; return 0; }