Dashboard/Coding patterns/13. Dynamic Programming

CODING PATTERNS · LESSON 13 OF 28 · 123 MIN VIDEO · 41 PROBLEMS

Dynamic Programming

Module Progress (0 / 41 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (123 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Dynamic Programming — How the Pattern Works

Dynamic Programming solves optimization, counting, and decision problems that exhibit optimal substructure and overlapping subproblems by decomposing them into smaller self-similar states and computing each distinct state exactly once. Whether implemented via bottom-up tabulation or top-down memoization, it maintains the topological invariant that every predecessor state referenced by a transition recurrence is finalized before the dependent state is evaluated. By collapsing identical subtrees of a recursive search graph into O(1) table lookups, DP reduces exponential O(2^n) or factorial O(n!) brute-force complexity to polynomial or pseudo-polynomial time (such as O(n), O(n * W), O(m * n), or O(n^3)).

WHEN TO USE THIS PATTERN
  • Prompts asking for an extremum (minimum cost, maximum profit, longest sequence), total count of ways, or boolean feasibility where local greedy choices fail due to downstream constraints.
  • Subset or multiset selection under an integer capacity or target-sum limit (0/1 or unbounded knapsack), where bounds like n <= 1000 and target <= 10^4 admit O(n * target) tabulation.
  • Two-sequence comparison, alignment, interleaving, or transformation (strings s1 and s2 of lengths m, n <= 2000), where matching prefixes s1[:i] and s2[:j] yields an O(m * n) grid recurrence.
  • Grid routing, tree coverage, DAG pathfinding, or bounded-hop graph traversal where transitions follow a strict partial order (monotone coordinates, post-order subtrees, strictly increasing cell values, or edge budget 1..k + 1).
  • Contiguous range or order-dependent elimination problems (n <= 500) where choosing the final operation or split index k inside nums[l..r] partitions the range into independent sub-intervals.
COMMON INTERVIEW PITFALLS
  • Sweeping capacity left-to-right in a single-row 0/1 knapsack: updating dp[c] from dp[c - w] in ascending order reads values already updated in the current item's pass, silently turning 0/1 selection into unbounded reuse; iterate c downward or read from an immutable previous row.
  • Violating dependency order in interval or goal-anchored DP: reading dp[i + 1][j - 1] or dp[i + 1][j] inside standard ascending row loops accesses uninitialized cells; always loop by increasing substring/interval length or reverse row indices when transitions point to larger row indices.
  • Corrupted sentinel values for unreachable states: initializing minimization tables with 0 or maximization tables with 0 when negative profits/scores exist lets invalid branches win min/max comparisons; use +inf (or amount + 1) for minimization, -inf for maximization, and dp[0] = 1 (or True) for counting/reachability seeds.
  • Off-by-one character indexing in padded prefix tables: when dp has dimensions (m + 1) x (n + 1) with index 0 representing the empty prefix, state dp[i][j] corresponds to characters s1[i - 1] and s2[j - 1], not s1[i] and s2[j].
Rolling-Window 1D TabulationLinear sequence recurrences where dp[i] depends only on a constant number of preceding states (e.g., dp[i - 1] and dp[i - 2]), compressing O(n) table memory to O(1).
def dp_rolling(nums):
    if not nums:
        return 0
    two_back, one_back = 0, nums[0]
    for x in nums[1:]:
        curr = max(one_back, two_back + x)
        two_back, one_back = one_back, curr
    return one_back
0/1 vs. Unbounded Knapsack TabulationSelecting items under capacity cap: reverse capacity iteration enforces single use per item (0/1), whereas forward capacity iteration allows unlimited item reuse (unbounded).
def knapsack_1d(weights, values, cap, unbounded=False):
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        span = range(w, cap + 1) if unbounded else range(cap, w - 1, -1)
        for c in span:
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]
Two-Sequence Prefix Grid DPAligning, matching, or editing two strings a and b of lengths m and n using a (m + 1) x (n + 1) table with row/column 0 reserved for empty prefixes.
def prefix_grid_dp(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 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[m][n]
Length-Ordered Interval DPContiguous subarray problems where dp[l][r] depends on shorter inner intervals dp[l][k - 1] and dp[k + 1][r], requiring outer iteration by increasing interval size.
def interval_dp(nums, cost):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for size in range(1, n + 1):
        for l in range(n - size + 1):
            r = l + size - 1
            for k in range(l, r + 1):
                left = dp[l][k - 1] if k > l else 0
                right = dp[k + 1][r] if k < r else 0
                dp[l][r] = max(dp[l][r], left + cost(l, k, r) + right)
    return dp[0][n - 1]
🔒 PRO PROBLEMTarget: O(key × ring²) time · O(ring) space

37. Freedom Trail

Pattern Trigger: greedy can trap you → best cost per position

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

With a table, how many additions does it take to reach Fibonacci term ten?