By themaskedhero, history, 3 years ago, ,

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

• +12

 » 3 years ago, # | ← Rev. 2 →   +28 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).
 » 3 years ago, # |   +5
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +5 Can it be done faster than O(mn)?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes, it can be solved in O(m3), which is better in this case.
 » 3 years ago, # |   0
 » 3 years ago, # |   +6 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