Knapsack and subset sums

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

0/1 knapsack permits each item once; unbounded knapsack permits reuse. State can be best value or reachability at a capacity. Compressed 0/1 updates descend so each item reads the previous item layer.

Work through an example

For one item 2 and target 4, descending updates reach 2 but not 4. Ascending would reuse the newly reached 2 and incorrectly reach 4.

Time and space complexity

O(nT) time/O(T) space for nonnegative integer target T; pseudo-polynomial in numeric T.

Why it works

At each item, descending states depend only on values before using that item.

Common mistakes

Ascending updates change 0/1 semantics.
Negative values require shifted/different state design.

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