To calculate nCr using Dynamic Programmimg

[niranjansy]

Description
The objective of this program is to calculate the value of nCr for given values of n and r. This can be done using the recursive formula:
nCr = (n-1)Cr + (n-1)C(r-1)
For big values of n and r, implementing this using a recursive function takes a very long time since there will be many overlapping sub-problems. So a solution to this would be to use dynamic programming, where we store intermediate results in a table, so that we do not have to compute the same sub-problem over and over again. The task here is to implement the above idea using dynamic programming.

Details
• Technical Specifications: Use C++ or C language for coding
• Type of issue: Single
• Time Limit: One day

Issue Requirements / Progress:

• Writing a dynamic programmimg algorithm to perform the above function

• For bigger values of n and r, since the output will be beyond the range of integer numbers, output the answer mod (10^9 + 7).

Resources

• https://www.geeksforgeeks.org/binomial-coefficient-dp-9/
• https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/

Directory Structure
Create a folder named '43'(43 as in the issue number) in the 'algorithms' folder. Name your program file as ‘nCrDynProg.cpp' or ‘nCrDynProg.c' accordingly. Add this program file to the folder '/algorithms/43'.

Note
Please claim the issue first by commenting here before starting to work on it.
Point of contact
While submitting a PR, request a review from Niranjan S Yadiyala @(niranjansy).

[fsabr]

I would like to take this up.
Could you give the constraints on 'n' and 'r'?

[niranjansy]

0 <= r <= n <=1000