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
A well-known problem is finding Longest Common Subsequence (LCS) of 2 strings , let's say string A and string B. If |A| ≤ 5000, |B| ≤ 10^6 then we cannot use the simple DP approach since its complexity is O( |A|.|B| ).
One observation is that, the length of LCS is indeed ≤ min( |A|,|B| ). Then instead of let dp[i][j]=k be the longest LCS when we consider first i characters of A and first j characters of B, we will let dp[i][k]=j meaning j is the smallest position in B so that it can form a LCS length k with first i characters of A.
This required a pre-processed array next[i][j] meaning the first position of character j in [i..|B|]. However, the complexity for DP now is O(|A|^2).
Nice one.
Given an array of n ≤ 106 positive integers, output the number of non-empty subsequences whose sum is divisible by a given 2 ≤ m ≤ 300, modulo 1000003. You may try it here.
Can it be done faster than O(mn)?
Yes, it can be solved in O(m3), which is better in this case.
Weights and Measures
The nlogn optimization for longest increasing subsequence swaps the state and value, optimizing for the smallest last value that has a certain length.
This is described here: https://en.wikipedia.org/wiki/Longest_increasing_subsequence