Help in Combinatorial DP Problem

Правка en1, от jhjfbsbfkbjfnfnfjfj, 2020-04-01 15:35:46

Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number M (1, 2 or 3) is fixed.]

T N C M

Sample Input:

3 5 3 1 5 2 2 6 2 3

Sample Output:

25 10 10

I defined dp[i][j] as the number of ways of distributing i coins to j charities. Then, a recursion relation should be derived in each of these three cases:

So for 1 at least 1 coin dp[i][j]=j∗dp[i−1][j]+dp[i−1][j−1]

I am unable to figure out the recurrence relation for at least 2 coins and at least 3 coins. Can you please explain the other two recurrence relation by clearly defining each states and transitions. I would be highly obliged to you and much of time will be saved.

Thank You

Теги #3d-dp, #dynamic programing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский jhjfbsbfkbjfnfnfjfj 2020-04-01 15:35:46 866 Initial revision (published)