Honestly's blog

By Honestly, history, 10 months ago, In English

While solving dp ,i think we have all solved the problem subset sum==target ,its pretty basic ,now what if there were q queries for different target sums,obviously the brute force wud be to reconfigure the dp array before each query ,but the whole process would then take O(N*Q*T) time ,which has a high chance of giving TLE, can you guys suggest ways to initialize the dp array only once ,and keep it constant across all queries ?

  • Vote: I like it
  • -13
  • Vote: I do not like it

»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

store the values of target left instead of sum we made.

»
10 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

use bitset :)