Dynamic programming O($N^3$)
Compute boolean array trans[i][j][t] = true (t=0..5) <=> s[i..j] can transform into A, B, AA, BB, AB, BA
Based on trans, we can easily compute f[i][j] = mininum length that s[i..j] can reduce to
Wednesday, October 14, 2009
Subscribe to:
Post Comments (Atom)
i didnt get the exact way how you are calculating trans[i][j][t]..i mean how are you using dp in there..?
ReplyDelete