Algorithms & Coding Interviews · Greedy, DP & Bits

DP on Grids & Knapsack

Grid DP and knapsack DP cover a huge share of medium interview problems. Learn the grid recurrences, the 0/1 vs unbounded knapsack loop directions, how partition and target-sum problems reduce to knapsack, and watch Unique Paths, Partition Equal Subset Sum and Maximal Square filled step by step.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 10 min read▶ 3 interactive🛠️ 4 exercises

🎯 What you'll learn

Grid DP and single-row space optimization
0/1 vs unbounded knapsack and why loop direction matters
Combinations vs permutations in counting problems
Six LeetCode problems with animated tables

📚 Before you start

DP fundamentals

Part 1The Pattern

Two families cover a huge share of medium DP problems. Grid DP: the answer for cell (r, c) depends on its neighbours above and to the left (paths, path sums, squares). Knapsack DP: you pick items under a budget (capacity, target sum), and dp[w] is the best result achievable with budget w. Both use 2D tables that can usually be squeezed into a single row, and the direction you loop in is part of the solution.

A unique-paths grid: each cell is the sum of the cell above and the cell to the left

1Grid DP

text

dp[r][c] = combine(dp[r-1][c], dp[r][c-1]) + cost(r, c)
first row / first column: only one way to arrive

Unique Paths: combine = + (count paths).
Minimum Path Sum: combine = min, plus the cell's cost.
Maximal Square: dp[r][c] = 1 + min(top, left, top-left) when the cell is 1.
Obstacles: a blocked cell gets 0 paths / infinity cost.

Since row r only needs row r − 1, keep one row and update it left to right: row[c] = row[c] (from above) + row[c-1] (from the left).

2Knapsack Variants

Variant	Example	Loop over budget
0/1 (each item at most once)	Partition Equal Subset Sum, Target Sum, Last Stone Weight II	backwards (high → low)
Unbounded (reuse items)	Coin Change, Coin Change II, Perfect Squares	forwards (low → high)
counting vs optimizing	"how many ways" sums; "best value" takes max/min	—
combinations vs permutations	items outer loop = combinations; budget outer loop = permutations	—

3Templates

typescript

function uniquePaths(m: number, n: number): number {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) for (let c = 1; c < n; c++) row[c] += row[c - 1];
  return row[n - 1];
}

function knapsack01(weights: number[], values: number[], cap: number): number {
  const dp = new Array(cap + 1).fill(0);
  weights.forEach((wt, i) => {
    for (let w = cap; w >= wt; w--) dp[w] = Math.max(dp[w], dp[w - wt] + values[i]);
  });
  return dp[cap];
}

function unbounded(weights: number[], values: number[], cap: number): number {
  const dp = new Array(cap + 1).fill(0);
  weights.forEach((wt, i) => {
    for (let w = wt; w <= cap; w++) dp[w] = Math.max(dp[w], dp[w - wt] + values[i]);
  });
  return dp[cap];
}

function knapDemo(m: number, n: number, weights: number[], values: number[], cap: number): number[] {
  return [uniquePaths(m, n), knapsack01(weights, values, cap), unbounded(weights, values, cap)];
}

python

def unique_paths(m, n):                      # grid DP: dp[r][c] = dp[r-1][c] + dp[r][c-1]
    row = [1] * n                            # one row is enough
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]             # row[c] (from above) + row[c-1] (from left)
    return row[-1]

def knapsack_01(weights, values, cap):       # each item at most once
    dp = [0] * (cap + 1)                     # dp[w] = best value with capacity w
    for wt, val in zip(weights, values):
        for w in range(cap, wt - 1, -1):     # BACKWARDS: each item used once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]

def unbounded(weights, values, cap):         # unlimited copies of each item
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for w in range(wt, cap + 1):         # FORWARDS: item can be reused
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[cap]

def knap_demo(m, n, weights, values, cap):
    return [unique_paths(m, n), knapsack_01(weights, values, cap), unbounded(weights, values, cap)]

Why the loop direction matters. With a single 1D array, dp[w − wt] must hold the value from before this item was considered (0/1) or possibly after (unbounded). Looping budget downward reads only old values, so each item is counted once; looping upward lets the item be used again in the same pass.

4Turning Problems Into Knapsack

Partition Equal Subset Sum: can some subset sum to total / 2? → 0/1 boolean knapsack.
Target Sum (+/− signs): a subset P with sum(P) − (total − sum(P)) = target → sum(P) = (total + target) / 2 → count subsets with that sum.
Last Stone Weight II: split stones into two groups as equal as possible → best subset sum ≤ total / 2.

Recognizing this reduction is what interviewers are really testing.

⚠️ Common Pitfalls

Wrong loop direction for 0/1 vs unbounded in 1D arrays.
Swapping loops in counting problems (Coin Change II counts combinations only with coins in the outer loop).
Forgetting first-row/first-column initialization in grid DP (or an obstacle cutting off the rest of the row).
Odd totals in partition problems: (total + target) must be even and non-negative.
Pseudo-polynomial complexity: O(n · capacity) is fine for capacity 10⁴, not for 10⁹.

📋 Quick Reference

text

grid: dp[r][c] = f(dp[r-1][c], dp[r][c-1]); 1-row: row[c] = f(row[c], row[c-1])
0/1 knapsack: for item: for w from cap down to wt: dp[w] = best(dp[w], dp[w-wt] + val)
unbounded: same with w from wt up to cap
count subsets with sum S: dp[0] = 1; dp[w] += dp[w - x] (backwards)
O(n · capacity) time, O(capacity) space

Part 2Interview Problems

Six problems: grid paths and costs, the three knapsack reductions (partition, signs, coin combinations), and the maximal square.

1Unique Paths (LeetCode 62)

🟠 Medium. A robot moves only right or down on an m × n grid. How many paths go from the top-left to the bottom-right?

text

m = 3, n = 7 → 28

Approach. paths(r, c) = paths(r − 1, c) + paths(r, c − 1), with 1 along the first row and column. One row of length n suffices. (Combinatorics also works: C(m + n − 2, m − 1).)

Complexity. O(m · n) time, O(n) space.

typescript

function uniquePaths(m: number, n: number): number {
  const row = new Array(n).fill(1);
  for (let r = 1; r < m; r++) for (let c = 1; c < n; c++) row[c] += row[c - 1];
  return row[n - 1];
}

python

def unique_paths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]
    return row[-1]

2Minimum Path Sum (LeetCode 64)

🟠 Medium. Find a path from top-left to bottom-right (moving right or down) minimising the sum of cell values.

text

[[1,3,1],[1,5,1],[4,2,1]] → 7   (1→3→1→1→1)

Approach. dp[r][c] = grid[r][c] + min(dp[r − 1][c], dp[r][c − 1]); the first row and column only have one predecessor. Update a single row in place.

Complexity. O(m · n) time, O(n) space.

typescript

function minPathSum(grid: number[][]): number {
  const n = grid[0].length;
  const row = new Array(n).fill(Infinity);
  row[0] = 0;
  for (const cells of grid) {
    row[0] += cells[0];
    for (let c = 1; c < n; c++) row[c] = cells[c] + Math.min(row[c], row[c - 1]);
  }
  return row[n - 1];
}

python

def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    row = [float("inf")] * n
    row[0] = 0
    for r in range(m):
        row[0] += grid[r][0]
        for c in range(1, n):
            row[c] = grid[r][c] + min(row[c], row[c - 1])   # above vs left
    return row[-1]

3Partition Equal Subset Sum (LeetCode 416)

🟠 Medium. Can the array be split into two subsets with equal sums?

text

[1,5,11,5] → true   ([1,5,5] and [11])

Approach. Only possible if the total is even; then ask whether some subset sums to total / 2. 0/1 boolean knapsack: can[s] |= can[s − x], iterating s downward so each number is used once. A bitset (bits |= bits << x) is a neat optimization.

Complexity. O(n · total) time, O(total) space.

typescript

function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const target = total / 2;
  const can = new Array(target + 1).fill(false);
  can[0] = true;
  for (const x of nums) for (let s = target; s >= x; s--) can[s] = can[s] || can[s - x];
  return can[target];
}

python

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    can = [True] + [False] * target
    for x in nums:
        for s in range(target, x - 1, -1):         # backwards: use x at most once
            can[s] = can[s] or can[s - x]
    return can[target]

4Target Sum (LeetCode 494)

🟠 Medium. Put + or − before each number. Count the expressions that evaluate to target.

text

[1,1,1,1,1], target 3 → 5

Approach. Let P be the numbers with +. Then sum(P) − (total − sum(P)) = target, so sum(P) = (total + target) / 2. Count subsets with that sum (0/1 counting knapsack). If total + target is odd or negative, the answer is 0.

Complexity. O(n · total) time, O(total) space.

typescript

function findTargetSumWays(nums: number[], target: number): number {
  const total = nums.reduce((a, b) => a + b, 0);
  if ((total + target) % 2 !== 0 || Math.abs(target) > total) return 0;
  const goal = (total + target) / 2;
  const ways = new Array(goal + 1).fill(0);
  ways[0] = 1;
  for (const x of nums) for (let s = goal; s >= x; s--) ways[s] += ways[s - x];
  return ways[goal];
}

python

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (total + target) % 2 or abs(target) > total:
        return 0
    goal = (total + target) // 2
    ways = [1] + [0] * goal                       # ways[s] = subsets summing to s
    for x in nums:
        for s in range(goal, x - 1, -1):
            ways[s] += ways[s - x]
    return ways[goal]

5Coin Change II (LeetCode 518)

🟠 Medium. Count the combinations of coins (unlimited supply) that make amount.

text

amount = 5, coins = [1,2,5] → 4

Approach. Unbounded counting knapsack: ways[a] += ways[a − c]. Put coins in the outer loop so each combination is counted once in a fixed coin order; swapping the loops would count permutations (1+2 and 2+1 separately).

Complexity. O(amount · k) time, O(amount) space.

typescript

function change(amount: number, coins: number[]): number {
  const ways = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (const c of coins) for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
  return ways[amount];
}

python

def change(amount, coins):
    ways = [1] + [0] * amount
    for c in coins:                              # outer: coins → combinations
        for a in range(c, amount + 1):           # forwards: reuse allowed
            ways[a] += ways[a - c]
    return ways[amount]

6Maximal Square (LeetCode 221)

🟠 Medium. In a 0/1 matrix, return the area of the largest square containing only 1s.

text

classic 4×5 matrix → 4 (a 2×2 square)

Approach. side[r][c] = side of the largest all-1 square with bottom-right corner at (r, c) = 1 + min(top, left, top-left) when the cell is 1, else 0. The smallest neighbour limits how far the square extends.

Complexity. O(m · n) time, O(n) space with a rolling row.

typescript

function maximalSquare(matrix: string[][]): number {
  const m = matrix.length, n = matrix[0].length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  let best = 0;
  for (let r = 1; r <= m; r++)
    for (let c = 1; c <= n; c++)
      if (matrix[r - 1][c - 1] === "1") {
        dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]);
        best = Math.max(best, dp[r][c]);
      }
  return best * best;
}

python

def maximal_square(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 0
    for r in range(1, m + 1):
        for c in range(1, n + 1):
            if matrix[r - 1][c - 1] == "1":
                dp[r][c] = 1 + min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1])
                best = max(best, dp[r][c])
    return best * best

🧠 Key takeaways

Grid DP: dp[r][c] from above and left; keep one row.
0/1 knapsack loops budget backwards; unbounded loops forwards.
Counting combinations: items in the outer loop; permutations: budget outer.
Partition / target sum / stone weight reduce to subset-sum knapsack.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

algo_dp_on_grids_and_knapsack_exercise_1.py

TS PY

algo_dp_on_grids_and_knapsack_exercise_2.py

TS PY

✅ Check yourself

Answer the questions — feedback is instant.

1. In a 1D 0/1 knapsack, why loop capacity downward?

Avoid reusing the item.

2. Coin Change II with amounts in the outer loop would count…

Loop order matters.

3. Target Sum reduces to counting subsets with sum…

P − (total − P) = target.

4. Maximal Square recurrence uses…

Smallest neighbour limits the square.

Source: algo_dp_on_grids_and_knapsack_theory_1.md, algo_dp_on_grids_and_knapsack_theory_2.md · generated by tools/build_lessons.py