State dependencies and space reduction

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

Space reduction follows the dependency graph. A two-prefix DP often needs previous row, current left, and old diagonal. Keep the diagonal before overwriting; preserve item-layer semantics for knapsack.

Work through an example

One-row LCS saves old dp[j] as next diagonal, compares current characters, then updates from old top and new left. Full reconstruction may still require a table or divide-and-conquer technique.

Time and space complexity

O(mn) time/O(n) value storage; reconstruction needs additional design.

Why it works

Old row values and new row values are never confused at a transition.

Common mistakes

Blindly changing loop direction can alter semantics.
Reusing one matrix row by aliasing does not create independent rows.

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