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