The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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^{th} 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 casesreturn getFibTerm1(n-1) + getFibTerm1(n-2);
}
// Dynamic programming solution
// Very efficient in terms of time complexityint 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 processingint 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];
}
// mainint main() {
int n = 6;
int nth_fib_term = getFibTerm2(n);
cout<<"Fib term :: "<<nth_fib_term;
cout<<endl;
return 0;
}

#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 casesreturn getFibTerm1(n-1) + getFibTerm1(n-2);
}
// Dynamic programming solution
// Very efficient in terms of time complexityint 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 processingint 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];
}
// mainint main() {
int n = 6;
int nth_fib_term = getFibTerm2(n);
cout<<"Fib term :: "<<nth_fib_term;
cout<<endl;
return 0;
}