Hello everyone I am stuck on this problem .
- 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 ?
You can rewrite the problem as such. Find all of these:
Each of these can be done by doing a completely classical textbook knapsack DP (and the recurrence you wrote is more-or-less exactly that.