Sequence DP

Single Sequence

Very similar to coordinate DP. Usually each element can represent its own state which can be defined either by prefix or suffix. The topological ordering can be tricky at times (more incoming edges than the grid).

Double Sequence

The subproblem is defined as how two strings/sequences compare to each other at (i, j) where i is the index for sequence A and j is the index for sequence B. Thus. we need to build a grid for the underlying graph structure. The topological ordering tends to be easy in this case (up to 3 incoming edges for each node).