Counting versus optimization

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

Counting adds numbers of constructions; optimization takes min/max; feasibility uses OR. Same-looking state grids can have different meanings and base identities. Count combinations versus ordered sequences deliberately.

Work through an example

ways[0]=1 for counting sums: the empty construction provides one base way. minCoins[0]=0; other states start infinity. For feasibility, reachable[0]=True.

Time and space complexity

Costs depend on states and transitions; exact counts can grow large and require big integers or a specified modulus.

Why it works

Every transition combines disjoint cases or valid alternatives according to the chosen objective.

Common mistakes

Adding counts from overlapping cases double-counts.
Using zero for impossible minimization states invents cheap answers.

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