Optimising DP using bitset in C++

Revision en2, by TimberLee, 2016-06-21 16:41:36

I recently read somewhere that some DP solutions like knapsack can be optimised and the overall complexity can be reduced by a factor of 32 using std::bitset in C++.

Can someone explain this optimisation and the kinds of DP on which this works ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English TimberLee 2016-06-21 16:41:36 7 Tiny change: ' in C++.\nCan somebody explain t' -> ' in C++.\n\nCan someone explain t'
en1 English TimberLee 2016-06-21 16:38:24 280 Initial revision (published)