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 letdp[i][j]=kbe the longest LCS when we consider first i characters of A and first j characters of B, we will letdp[i][k]=jmeaning 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 isO(|A|^2).Nice one.

Given an array of

n≤ 10^{6}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(m^{3}), 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