Swapping DP State Problems

Revision en1, by themaskedhero, 2016-12-06 22:38:31

I've seen this technique before where if you have some recurrence dp(state) = val, you can swap the state and value functions to better the complexity, and instead get dp(val) = state.

I'm looking for examples of these problems, one example is http://usaco.org/index.php?page=viewproblem2&cpid=648 .



  Rev. Lang. By When Δ Comment
en1 English themaskedhero 2016-12-06 22:38:31 343 Initial revision (published)