Help needed in Atcoder Dp Question

Revision en2, by Jalboss, 2020-07-21 14:17:02

Hello everyone I am stuck on this problem .

  1. Please help me by explaining the dp recurrence and also if this can be solved by dp + bitmask technique.

The dp recurrence looks like this : Let dp[i][j][k] be the number of ways to choose j numbers among the first i numbers such that the sum becomes k. You can update this array from smaller i, and when i > 0, dp[i][j][k] = dp[i−1][j][k]+dp[i−1][j −1][k−xi]. (Make sure that you don’t access to negative indices). Then, the answer is the sum of dp[N][t][At] for 0 ≤ t ≤ N.

Can somebody explain me this ?

Tags #dynamic programming, #backtracking, #recursion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Jalboss 2020-07-21 14:28:48 2 Tiny change: ' this : \nLet dp[i' -> ' this : \n\nLet dp[i'
en2 English Jalboss 2020-07-21 14:17:02 382
en1 English Jalboss 2020-07-21 13:47:11 330 Initial revision (published)