Subsequence states

What is multidimensional DP?

Multidimensional dynamic programming uses more than one quantity to describe a smaller problem. Two states with the same first quantity can still need different answers, so the second quantity matters. A table can store these answers by their coordinates. Each entry must have a clear meaning before you fill it.

Example: On a grid where movement is only right or down, ways(row, column) counts routes to that cell. It depends on the cell above and the cell to the left, so both row and column identify the state.

Helpful before this chapter

If these ideas are new, begin with:

One-dimensional dynamic programming

Understand the idea

Subsequence states preserve order while allowing skips. LCS uses a match plus the best shorter prefixes, or skips one side on mismatch. LIS can use dp ending at i or a separate minimal-tail representation.

Work through an example

For a[i-1]==b[j-1], LCS adds one to dp[i-1][j-1]; otherwise max(top,left). A substring would instead require consecutive matching and reset on mismatch.

Time and space complexity

LCS O(mn); simple LIS O(n²), binary-search-tail LIS O(n log n).

Why it works

The table value is a length, not necessarily the actual sequence.

Common mistakes

The LIS tails array is not necessarily a valid recovered subsequence.
Contiguous substring uses another recurrence.

Chapter lab · Python implementation

Multiple coordinates describe subproblems involving two prefixes, grid positions, or item-and-capacity choices. Our lab computes longest common subsequence with a full table and solves 0/1 subset sum with a descending one-dimensional update. The direction of updates expresses whether an item may be reused.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def lcs(a,b):
    dp=[[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(1,len(a)+1):
        for j in range(1,len(b)+1):
            if a[i-1]==b[j-1]: dp[i][j]=dp[i-1][j-1]+1
            else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[-1][-1],dp

def subset_sum(values,target):
    if target<0 or any(x<0 for x in values):
        raise ValueError('nonnegative values required')
    possible=[False]*(target+1); possible[0]=True
    for x in values:
        for total in range(target,x-1,-1):
            possible[total]=possible[total] or possible[total-x]
    return possible[target]

def grid_paths(rows,cols):
    if rows<1 or cols<1: return 0
    dp=[1]*cols
    for _ in range(1,rows):
        for c in range(1,cols): dp[c]+=dp[c-1]
    return dp[-1]

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert lcs('abcde','ace')[0]==3
assert lcs('','abc')[0]==0
assert subset_sum([1,5,11,5],11)
assert not subset_sum([2],4)
assert subset_sum([],0)
assert grid_paths(3,3)==6 and grid_paths(0,3)==0

CHECK YOUR UNDERSTANDING