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...
3 comments:
hey...nice example..could you please mention some more examples of DP..
Here's a similar DP-type thing you can use: nCk = nC(k-1) * (n-k)/k.
The advantage of this method is that it's still O(1) to calculate a given value given all "smaller" ones, but here the set of "smaller" values is comprised only of binomial coefficients with the same value of n.
For example, you could calculate 200C100 using only 200Ck for 1 <= k <= 99, rather than having to calculate nCk for all 0 <= n <= 99 and 0 <= k <= n.
@dysfunctionalequations
Thats pretty correct...thanks for sharing this..anyways my only motive here was to illustrate an example of DP and thats why I mentioned this example here..but your optimization is quite good.. :)
Post a Comment