Need help in a counting problem

Revision en2, by hossainzarif, 2020-08-27 09:20:49

Problem
I got this idea. $$$dp[i][j]$$$ be the number of ways to divide j people with the group of size $$$A$$$ to size $$$j$$$.
$$$dp[i][0] = 1$$$ and $$$dp[i][j] = dp[i - 1][j] + \sum\limits_{k = C}^D\binom{j}{k * i} * dp[i - 1][j - k * i] * \dfrac{(k * i)!} {(i!)^k * k!}$$$
This has a complexity of $$$O(n^3logn)$$$ which won't pass. How to improve it to $$$O(n^2logn)$$$ or $$$O(n^2)$$$
code

Tags #dp, #counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English hossainzarif 2020-08-27 09:20:49 38 Tiny change: 'r $O(n^2)$' -> 'r $O(n^2)$ \n[code](https://ideone.com/2BVewv)'
en1 English hossainzarif 2020-08-27 09:19:22 457 Initial revision (published)