nCr= (n)!/(n-r)!(r)!
if suppose you have to calculate combinations of numbers repeatedly in a program, this approach can be very time consuming, so lets do this by dynamic programming... :)
Once the following table is built, we can retrieve combination of any number in O(1) time..
In order to solve it by DP, we gotta follow those two rules as explained in an earlier post..
1) an optimal substructure
we can build a bottom up approach in the following manner,by the formula, nCr=(n-1)Cr + (n-1)C(r-1),
which implies that in order to calculate factorial of n, if we know factorial of n-1, then nCr can easily be done....so this shows that the final solution is actually build up from various sub problems.
2) an overlapping subproblem
Secondly, the subproblems will be repeated many a times. I shall explain this below in more detail.
So lets solve the problem now...!!!!
let j denote the column values and i denote the row values.
so if j=6, and i=4, so 6C4 = arr[4][6] =15
In the above figure, we can easily find combination of any number till 10.in order to build this table, just follow the following operation,
for(int i=1;i<=10;i++)
arr[0][i]=i;
if(i>j)
arr[i][j]=0;
else
arr[i][j]=arr[i][j-1]+arr[i-1][j-1];
the statement "arr[i][j]=arr[i][j-1]+arr[i-1][j-1];"shows that all present combinations are acheived from some previous operations.
Work on this example a little more, try it for bigger numbers and I am sure u wil start admiring Dynamic Programming all the more...
For any queries, do let me know...
