themaskedhero's blog

Swapping DP State Problems
By themaskedhero, history, 8 years ago, In English

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

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 6   Vote: I like it +28 Vote: I do not like it

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).

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice one.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Weights and Measures

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply