Leetcode Problem 1692. Count Ways to Distribute Candies

1692. Count Ways to Distribute Candies

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D array dp with dimensions (k+1) x (n+1) and fill it with zeros.
  2. Set dp[i][i] to 1 for all i from 1 to k because there is only one way to distribute i candies into i bags.
  3. Iterate over the number of bags i from 1 to k.
  4. For each i, iterate over the number of candies j from i+1 to n.
  5. Update dp[i][j] using the recurrence relation: dp[i][j] = (i * dp[i][j-1] + dp[i-1][j-1]) % mod where mod is 10^9 + 7.
  6. After filling the dp array, return dp[k][n] as the answer.
UML Thumbnail

Inclusion-Exclusion Principle Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...