~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

2-D dynamic programming

Interval (range) DP

dp[l][r] over subarrays, filled by increasing length; pick the split point.

Visual guide Quiz (9) Spot the pattern
Notes

Recognise it when: the answer for [l, r] depends on how you split it: bursting balloons, cutting a stick, merging stones, palindromic subsequences.

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        dp[l][r] = best(dp[l][k] + dp[k][r] + cost(l, k, r) for k in range(l + 1, r))

O(n^3) typically.

Key trick for burst balloons: k is the balloon burst last within (l, r), so its neighbours at that moment are l and r. Add sentinel 1s at both ends.

Gotchas: fill by increasing length, not by l then r.

6 problems

Interview roadmap

2-D dynamic programming Grids, two strings, knapsacks, ranges.

Interval (range) DP guide

esc