count-ways-to-distribute-candies

< Previous 　　　　　　　　　　　　　　　　 Next >

1692. Count Ways to Distribute Candies (Hard)

Related Topics

[Dynamic Programming]

Hints

Hint 1

Try to define a recursive approach. For the ith candies, there will be one of the two following cases:

Hint 2

If the i - 1 previous candies are already distributed into k bags for the ith candy, you can have k * dp[n - 1][k] ways to distribute the ith candy. We need then to solve the state of (n - 1, k).

Hint 3

If the i - 1 previous candies are already distributed into k - 1 bags for the ith candy, you can have dp[n - 1][k - 1] ways to distribute the ith candy. We need then to solve the state of (n - 1, k - 1).

Hint 4

This approach will be too slow and will traverse some states more than once. We should use memoization to make the algorithm efficient.