#### Dynamic Programming

Problem
Find the nth 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 nth 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 0th term is stored. For e.g, fib [ 2 ] stores the 2nd term of fibonacci series. Finally, fib [ n ] gives the nth term.
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;
}```