Sequence comparison

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

Sequence DP uses states for two prefixes. Matching characters may take a diagonal dependency; mismatches may delete, insert, skip, or replace depending on the problem. The recurrence must follow the exact objective.

Work through an example

LCS('abcde','ace') returns 3. Edit distance instead minimizes insert/delete/replace counts and uses nonzero empty-prefix bases.

Time and space complexity

O(mn) time/O(mn) table; rolling rows can reduce value-only space to O(min(m,n)).

Why it works

Each cell summarizes the optimum relation between the two selected prefixes.

Common mistakes

LCS and edit distance have different transitions.
Boundary rows express operations on an empty prefix.

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