### I_am_Vengeance's blog

By I_am_Vengeance, history, 12 months ago,

Can anyone please explain how this problem can be solved in top-down manner (Recursive dp).

• +9

 » 12 months ago, # |   +1 Check the following implementation for small values of $K$ and $a_i$. Recurive dp solutionCandies
•  » » 12 months ago, # ^ |   0 Thanks for you help!
 » 12 months ago, # |   +1 Let dp[i][j] represent how many ways possible to distribute exactly j candies among first i participants. so dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]........+dp[i-1][j-a[i]].Calculating this sum if you are using loop will lead to O(n*k*k)So you prefix sum instead . This prefix sum can be the dp array itself or another 2d arrayImplementataion:Using dp as prefix array only:here and below is the main part  for(int i=1;i
•  » » 12 months ago, # ^ |   0 I was looking for a recursive solution, thanks nonetheless.
 » 12 months ago, # | ← Rev. 5 →   +1 let $dp[i][j]$ = the number of ways to share $j$ candies among the remaining kids. We can write a $O(K * K * N)$ DP: Code 1int solve(int i, int j) { if (j < 0) return 0; if (i == n) return (j == 0) ? 1 : 0; if (dp[i][j] != -1) return dp[i][j]; int ans = 0; for (int put = 0; put <= a[i]; put++) { ans = ans + solve(i + 1, j - put); ans %= mod; } return dp[i][j] = ans; } However, this is too slow and will result in TLE. To optimize this, let's calculate all possible states starting from the $(i + 1)$-th kid before calculating any state starting from the $i$-th kid. We can see that $dp[i][j]$ = ($dp[i + 1][j]$ + $dp[i + 1][j - 1]$ + ... + $dp[i + 1][j - limit]$), limit is $min(j, a[i])$. If we store the prefix sum of states starting from the $(i + 1)$-th kid, we can compute the DP transition in $O(1)$ and reduce the complexity to $O(K * N)$. Final codeint solve(int i, int j); void calc(int i) { sum[i][0] = solve(i, 0); for (int j = 1; j <= k; j++) sum[i][j] = (sum[i][j - 1] + solve(i, j)) % mod; } int solve(int i, int j) { if (i == n) return (j == 0) ? 1 : 0; if (dp[i][j] != -1) return dp[i][j]; int ans = 0, limit = min(j, a[i]); if (sum[i + 1][j] == -1) calc(i + 1); ans = (ans + sum[i + 1][j]) % mod; if (j - limit - 1 >= 0) ans = (ans - sum[i + 1][j - limit - 1] + mod) % mod; return dp[i][j] = ans; } Submission: Link
•  » » 12 months ago, # ^ |   0 Thanks! got it now
•  » » 5 weeks ago, # ^ |   0 thanks bro really nice solution ,, i was searching for this solution for around 2 hrs