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 .

Thanks