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

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;
}

Back | Next

All problems on Dynamic Programming
* Find the nth term of fibonacci series
* Evaluate combination(n, r)
* Solve the Edit-Distance problem
* Longest Common Subsequence ( LCS ) problem
* Given a set of coin denominations, find the minimum number of coins required to make a change for a target value
* Longest Increasing Subsequence ( LIS ) problem
* Unbounded Knapsack problem
* 0/1 Knapsack problem
* Splitting a string into minimum number of palindromes