hossainzarif's blog

By hossainzarif, history, 4 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it