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 :-
Evaluate nCr i.e combination ( n, r ).
Combination refer to the combination of n things taken r at a time without repetition.
Mathematically, nCr = n! / r! * ( n - r )!

Solution :-
Let C ( n , r ) denotes combination of n things taken r at a time.
As per recursive formulation, C ( n , r ) = C ( n - 1 , r - 1 ) + C ( n - 1 , r ) with C ( n , 0 ) = C ( n , n ) = 1.
This is basically the structure of an optimal solution defined recursively.
We can maintain a 2D array C [ n + 1 ][ r + 1 ] which stores all the combination values starting from C ( 0 , 0 ). Finally, C [ n ][ r ] gives the value of C ( n , r ).
See the program below for the solution.

#include<iostream>
using namespace std;

// find C(n,r)
// Standard recursive formula for computing C(n,r)
// C(n,r) = C(n-1,r-1) + C(n-1,r)
// where C(n,0) = C(n,n) = 1
int choose(int n,int r) {
   if(r == 0 || r == n)
      return 1;
   // store C(n,r) in a matrix   
   int c[n+1][r+1];
   int i,j;
   for(i=0;i<=n;i++) {
      // C(i,0) = 1 for i = 0...n  
      c[i][0] = 1;
   }
   for(j=0;j<=r;j++) {
      // if n = 0, C(n,r) = 0 for all 'r'
      c[0][j] = 0;
   }
   for(i=1;i<=n;i++) {
      for(j=1;j<=r;j++) {
         if (i == j) {
            // C(n,n) = 1
            c[i][j] = 1;
         }
         else if (j > i) {
            // case when r > n in C(n,r)        
            	c[i][j] = 0;
         }
         else {
            // apply the standard recursive formula        
            c[i][j] = c[i-1][j-1] + c[i-1][j];
         }
      }
   }
   return c[n][r];
}

// main
int main() {
   int n = 5,r = 2;
   int comb = choose(n,r);
   cout<<"C("<<n<<","<<r<<") :: "<<comb;
   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