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| ≤ 106 then we cannot use the simple dynamic programming approach since its complexity would be O(|A|.|B|).
One observation is that, the length of LCS is indeed ≤ min(|A|, |B|). Then, instead of letting 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 of length k with first i characters of A.
This requires a pre-processed array next[i][j] meaning the first position of character j in [i..|B|]. However, the complexity for DP now is reduced to 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