Why cant this question be done with 1-D DP like 0-N knapsack

#1
#2

Hello @aryanv

You can solve this question using 1-D DP.
Your code has some errors.

  1. You should take as input “w” integers and NOT “n”. Read the input format.
  2. Change every “int” to “long long int” because at line 18 when you do “dp[i-j-1] + arr[j]”, this value can go beyond the range of “int” because “dp[i-j-1]” can be “INT_MAX”;

Here is the modified code.

1 Like