Need help in a counting problem

Правка en1, от hossainzarif, 2020-08-27 09:19:22

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)$$$

Теги #dp, #counting

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский hossainzarif 2020-08-27 09:19:22 457 Initial revision (published)