Quy hoạch độngDynamic Programming

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

Dynamic programming (DP) is what you get when you take a recursive solution that recomputes the same subproblems over and over, and make it stop doing that. That is the whole idea. Everything else — tables, state design, rolling arrays, the intimidating vocabulary — is machinery built around that one observation.

The name is historical and actively misleading. Richard Bellman coined it in the 1950s while working at RAND; “programming” meant planning (as in “linear programming”), not writing code, and “dynamic” was chosen partly because it sounded impressive enough to survive a defence-budget review. The underlying mathematical statement is Bellman’s principle of optimality: an optimal policy has the property that whatever the initial state and initial decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. Stripped of the formality: if the best route from Hanoi to Ho Chi Minh City goes through Da Nang, then the portion from Da Nang to Ho Chi Minh City is itself the best route between those two cities.

DP sits between two techniques already covered in this section. Divide and conquer also breaks a problem into subproblems, but its subproblems are disjoint — merge sort’s two halves share nothing, so there is nothing to cache. Greedy algorithms also exploit optimal substructure, but they commit to one choice at each step and never reconsider. DP is the middle ground: subproblems overlap, so caching pays; and you cannot pick the right choice locally, so you try all of them — but only once each.

The payoff is usually a jump from exponential to polynomial. Naive recursive Fibonacci is O(φⁿ); memoized it is O(n). Naive recursive knapsack is O(2ⁿ); tabulated it is O(n·W). That is not a constant-factor win, it is the difference between “runs” and “does not run”.

Fundamentals

The two prerequisites

A problem admits a dynamic programming solution if and only if it has both of these properties. Checking for them is the first thing you should do, and it takes about thirty seconds.

1. Optimal substructure. The optimal solution to the problem can be built from optimal solutions to its subproblems. Formally, if OPT(S) is the optimal value for instance S, there is a recurrence expressing OPT(S) in terms of OPT of strictly smaller instances.

This is the property that lets you write a recurrence at all. Shortest path has it: if the shortest s→t path passes through v, its s→v prefix is a shortest s→v path (otherwise splice in the better prefix and get a shorter s→t path — a contradiction). Longest simple path does not have it: the longest simple path from A to D might go A→B→C→D, but the longest simple path from A to C might be A→D→B→C, which uses D and therefore cannot be extended to D. The subproblems interfere with each other, so no recurrence over “longest path to v” is valid, and indeed longest simple path is NP-hard.

2. Overlapping subproblems. The recursion tree revisits the same subproblem many times. This is what makes caching worthwhile.

Look at fib(5) expanded naively:

                     fib(5)
                 /            \
            fib(4)             fib(3)
           /      \           /      \
      fib(3)     fib(2)   fib(2)    fib(1)
      /    \     /    \   /    \
  fib(2) fib(1) f(1) f(0) f(1) f(0)
   /   \
 f(1)  f(0)

fib(3) is computed twice, fib(2) three times, fib(1) five times. The tree has roughly φⁿ ≈ 1.618ⁿ nodes but only n + 1 distinct values in it. Every recomputation is waste. Merge sort’s tree, by contrast, has O(n log n) nodes and no two subproblems are ever the same interval — nothing to cache, so divide and conquer is the right tool there, not DP.

Top-down (memoization) versus bottom-up (tabulation)

There are two ways to implement the same recurrence. They compute identical values and have identical asymptotic complexity; they differ in ergonomics and constant factors.

Top-down / memoization is the recursive formulation plus a cache. You write the recurrence exactly as you derived it, and check the cache before recursing.

Bottom-up / tabulation iterates over states in an order that guarantees every dependency is already computed, filling a table. There is no recursion and no call stack.

Here is the same problem — coin change, minimum number of coins to make amount — written both ways so the correspondence is visible line by line.

from functools import lru_cache

INF = float("inf")

def coin_change_topdown(coins, amount):
    """Top-down: the recurrence, written literally, with a cache in front of it.
    Time O(amount * len(coins)), space O(amount) for the cache + O(amount) call stack."""
    memo = {}

    def best(rem):
        if rem == 0:
            return 0                      # base case: nothing left to pay
        if rem < 0:
            return INF                    # overshot — this branch is invalid
        if rem in memo:                    # <-- the only line that makes it DP
            return memo[rem]
        result = INF
        for c in coins:
            result = min(result, 1 + best(rem - c))
        memo[rem] = result
        return result

    answer = best(amount)
    return -1 if answer == INF else answer


def coin_change_bottomup(coins, amount):
    """Bottom-up: same recurrence, but states are visited in increasing order of `rem`,
    so every dependency (rem - c, which is smaller) is already final when we read it.
    Time O(amount * len(coins)), space O(amount), no recursion."""
    dp = [INF] * (amount + 1)
    dp[0] = 0                              # same base case
    for rem in range(1, amount + 1):
        for c in coins:
            if c <= rem and dp[rem - c] + 1 < dp[rem]:
                dp[rem] = dp[rem - c] + 1
    return -1 if dp[amount] == INF else dp[amount]


assert coin_change_topdown([1, 3, 4], 6) == 2      # 3 + 3, not 4 + 1 + 1
assert coin_change_bottomup([1, 3, 4], 6) == 2
assert coin_change_bottomup([2], 3) == -1

Note that [1, 3, 4] with amount = 6 is exactly the case where the obvious greedy (always take the largest coin that fits) fails: greedy gives 4 + 1 + 1 = 3 coins, the optimum is 3 + 3 = 2. Greedy happens to be correct for the US/EUR/VND denomination systems, which is why people are surprised when it breaks — see greedy algorithms for why “it works on my examples” is not an argument.

In Python, @lru_cache(maxsize=None) (or @functools.cache on 3.9+) gives you memoization for free on any function with hashable arguments. It is what you would actually use for a first pass:

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Two caveats before you reach for it in production. First, recursion depth: fib(10000) will hit Python’s default limit of 1000 frames and raise RecursionError, and raising sys.setrecursionlimit risks a real C-stack segfault. Second, the cache is attached to the function object, so it persists across calls and across test cases — if the memoized function closes over problem-specific data, stale entries will silently return wrong answers. Bottom-up has neither problem.

Designing the state and the transition

This is the part that is actually hard. The implementation is mechanical once you have the recurrence; getting the recurrence means answering four questions in order.

1. What is the state? The minimal set of parameters that fully determines the answer to a subproblem. “Minimal” matters in both directions: too few and the recurrence is wrong (different situations collapse into the same state), too many and you blow up the table. Ask: if I paused the algorithm here, what would I need to know to continue? For knapsack that is “which item am I considering, and how much capacity is left” — not the specific set of items already taken.

2. What is the transition? How is dp[state] computed from smaller states? This is the recurrence. It almost always comes from enumerating the choices available at this state: take this item or skip it, match these characters or insert/delete/replace, use this coin or move on.

3. What are the base cases? The states small enough to answer directly — usually empty input, or zero remaining capacity. Getting these wrong is the single most common DP bug, and it usually shows up as an off-by-one at the boundary of the table.

4. What is the evaluation order? For bottom-up, an order in which every state’s dependencies come first. If dp[i] depends on dp[i-1], iterate i upward. If it depends on dp[i+1], iterate downward. If the dependency graph is not a DAG, the problem is not DP as stated.

A useful sanity check: the total work is (number of states) × (work per transition). That product is your time complexity. If you can count states and count choices, you know the complexity before writing a line of code — and if the product is too big, you know to redesign the state before wasting time implementing it.

Key Concepts

Family 1 — Linear DP on one index: Fibonacci and climbing stairs

The simplest state space is a single integer. Both problems below have the identical recurrence dp[i] = dp[i-1] + dp[i-2]; only the base cases differ, which is a good early lesson that “which problem is this” often reduces to “which recurrence is this”.

def fib(n):
    """dp[i] = dp[i-1] + dp[i-2]; dp[0]=0, dp[1]=1.
    Time O(n), space O(1) — only the last two values are ever needed."""
    prev, cur = 0, 1                      # dp[0], dp[1]
    for _ in range(n):
        prev, cur = cur, prev + cur
    return prev


def climbing_stairs(n):
    """Number of ways to reach step n taking 1 or 2 steps at a time.
    To be standing on step i you arrived from i-1 (one step) or i-2 (two steps),
    and those two sets of paths are disjoint, so the counts add.
    Time O(n), space O(1)."""
    if n <= 2:
        return n
    one_back, two_back = 2, 1             # ways to reach step 2 and step 1
    for _ in range(3, n + 1):
        one_back, two_back = one_back + two_back, one_back
    return one_back


assert [fib(i) for i in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
assert climbing_stairs(5) == 8

Both are already space-optimized: the recurrence reaches back exactly two positions, so a two-variable rolling window suffices. This is the smallest instance of the rolling-array idea developed below. (Fibonacci also has an O(log n) matrix-exponentiation solution and a closed form, but neither generalizes to DP problems, so they are curiosities here rather than technique.)

Family 2 — Unbounded choices: coin change

Already shown above. Two variants worth separating because they are easy to confuse:

• Minimum coins (above) — loop order does not matter, because each state takes a min over all coins independently.
• Number of ways to make the amount — loop order matters enormously.

def coin_change_count_combinations(coins, amount):
    """Counts unordered combinations: {1,2} and {2,1} count once.
    The coin loop is OUTSIDE, so each coin is 'introduced' once and no
    permutation of an earlier coin set can be recounted.
    Time O(amount * len(coins)), space O(amount)."""
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                        # outer: coins
        for rem in range(c, amount + 1):   # inner: amounts, ascending (unbounded use)
            dp[rem] += dp[rem - c]
    return dp[amount]


def coin_change_count_permutations(coins, amount):
    """Counts ordered sequences: {1,2} and {2,1} count separately.
    The amount loop is OUTSIDE, so every coin can be the 'last' one at every amount.
    Time O(amount * len(coins)), space O(amount)."""
    dp = [0] * (amount + 1)
    dp[0] = 1
    for rem in range(1, amount + 1):       # outer: amounts
        for c in coins:                    # inner: coins
            if c <= rem:
                dp[rem] += dp[rem - c]
    return dp[amount]


assert coin_change_count_combinations([1, 2, 5], 5) == 4   # 5, 2+2+1, 2+1+1+1, 1x5
assert coin_change_count_permutations([1, 2, 5], 5) == 9

Swapping two for lines changes the answer from 4 to 9. This is the classic “my DP is subtly wrong and I cannot see why” bug, and the fix is always to ask what does the outer loop mean — the outer loop defines which dimension of the state you are advancing.

Family 3 — 0/1 knapsack

Given n items with weights and values, and a capacity W, maximize total value with each item used at most once.

State: dp[i][w] = best value using only the first i items with capacity w. Transition: for item i, either skip it (dp[i-1][w]) or take it (value[i] + dp[i-1][w - weight[i]], if it fits).

def knapsack_2d(weights, values, capacity):
    """Full 2D table — the version to write first, and the one you need
    if you want to reconstruct which items were chosen.
    Time O(n*W), space O(n*W)."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                       # choice A: skip item i
            if wi <= w:                                    # choice B: take item i
                dp[i][w] = max(dp[i][w], vi + dp[i - 1][w - wi])
    return dp[n][capacity]


def knapsack_1d(weights, values, capacity):
    """Rolling array. dp[w] holds row i-1 while we compute row i in place.
    The capacity loop MUST run downward: dp[w - wi] must still be the value
    from the previous row (item i not yet used). Iterating upward would let
    the same item be picked twice, silently turning this into unbounded knapsack.
    Time O(n*W), space O(W)."""
    dp = [0] * (capacity + 1)
    for wi, vi in zip(weights, values):
        for w in range(capacity, wi - 1, -1):              # descending — critical
            dp[w] = max(dp[w], vi + dp[w - wi])
    return dp[capacity]


w = [1, 3, 4, 5]
v = [1, 4, 5, 7]
assert knapsack_2d(w, v, 7) == 9      # items with weight 3 and 4
assert knapsack_1d(w, v, 7) == 9

The O(n·W) complexity deserves a warning: this is pseudo-polynomial, not polynomial. W is a value, and its encoding takes log W bits, so the running time is exponential in the input size. Knapsack is NP-hard; DP does not change that, it just performs well when W happens to be small. With W = 10⁹ and n = 100 the table has 10¹¹ cells and the algorithm is useless — that is the signal to switch to a value-indexed DP (dp[value] = minimum weight) or an approximation scheme.

Family 4 — Two sequences: LCS and edit distance

When the input is two strings or arrays, the state is almost always “a prefix of each”: dp[i][j] covers a[:i] and b[:j]. That single habit solves most string DP problems.

Longest common subsequence — the longest sequence appearing in both, in order but not necessarily contiguously.

def lcs_length(a, b):
    """dp[i][j] = LCS length of a[:i] and b[:j].
    If the last characters match, they can safely be paired (exchange argument:
    any LCS can be rewritten to use that pair), so dp[i][j] = dp[i-1][j-1] + 1.
    Otherwise drop one character from one side and take the better option.
    Time O(n*m), space O(n*m)."""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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[n][m]


assert lcs_length("ABCBDAB", "BDCABA") == 4     # e.g. "BCBA"

The filled table for a = "ABCB", b = "BDCB" — the row and column of empty prefixes are zero, and the answer sits in the bottom-right corner:

        ""  B   D   C   B
    "" [ 0  0   0   0   0 ]
    A  [ 0  0   0   0   0 ]
    B  [ 0  1   1   1   1 ]
    C  [ 0  1   1   2   2 ]
    B  [ 0  1   1   2   3 ]   <- LCS("ABCB","BDCB") = 3  ("BCB")

Edit distance (Levenshtein) — the minimum number of single-character insertions, deletions, or substitutions to turn a into b. Same prefix state, three choices instead of two.

def edit_distance(a, b):
    """dp[i][j] = cost to turn a[:i] into b[:j].
    Base cases: turning a prefix into "" costs one deletion per character,
    and "" into a prefix costs one insertion per character.
    Time O(n*m), space O(n*m)."""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i                               # delete all of a[:i]
    for j in range(m + 1):
        dp[0][j] = j                               # insert all of b[:j]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]        # free: characters already agree
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],                  # delete a[i-1]
                    dp[i][j - 1],                  # insert b[j-1]
                    dp[i - 1][j - 1],              # replace a[i-1] with b[j-1]
                )
    return dp[n][m]


def edit_distance_rolling(a, b):
    """Same recurrence, two rows instead of n+1. Time O(n*m), space O(min(n,m))
    after swapping so that b is the shorter string."""
    if len(b) > len(a):
        a, b = b, a
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[len(b)]


assert edit_distance("kitten", "sitting") == 3
assert edit_distance_rolling("kitten", "sitting") == 3

This is not a toy: edit distance is how spell checkers rank suggestions, how git diff and diff find minimal changesets (via LCS), and how bioinformatics aligns DNA sequences (Needleman–Wunsch is edit distance with a scoring matrix).

Family 5 — Longest increasing subsequence, twice

The O(n²) version is the natural DP: dp[i] = length of the longest increasing subsequence ending at index i.

def lis_quadratic(nums):
    """dp[i] = LIS length ending exactly at i. To extend, look back at every
    j < i with nums[j] < nums[i]. Time O(n^2), space O(n)."""
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

The O(n log n) version abandons the DP table for a greedy invariant plus binary search. Maintain tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1 seen so far. tails is strictly increasing by construction, so it can be binary-searched.

from bisect import bisect_left

def lis_nlogn(nums):
    """tails[k] = smallest tail of an increasing subsequence of length k+1.
    For each x: if it beats every tail, it extends the longest run (append);
    otherwise it replaces the first tail >= x, making that length cheaper to
    extend later without changing any length.
    Time O(n log n) — one binary search per element. Space O(n).
    NOTE: `tails` is NOT itself a valid subsequence; only its LENGTH is the answer."""
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)        # use bisect_right for non-decreasing LIS
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)


nums = [10, 9, 2, 5, 3, 7, 101, 18]
assert lis_quadratic(nums) == 4            # [2, 3, 7, 18] or [2, 3, 7, 101]
assert lis_nlogn(nums) == 4
assert lis_nlogn([7, 7, 7, 7]) == 1

Why replacing is safe: swapping a smaller value into tails[pos] never shortens anything already achievable, and it makes future extensions of that length strictly easier. The bisect_left/bisect_right choice encodes strict versus non-strict increase, and getting it backwards is the standard bug — [7,7,7,7] returns 1 with bisect_left and 4 with bisect_right. bisect is a C-implemented stdlib module and is exactly what you would use in production; hand-rolling the binary search buys nothing but bugs (see search algorithms).

If you need the actual subsequence and not just its length, tails is not enough — you must record, for each element, the index of its predecessor and the length it achieved, then walk backwards from the element that achieved the maximum. The reconstruction section below shows the general technique.

Family 6 — Grid DP

Grids are the friendliest DP because the state is literally the cell you are standing in and the dependency order is “left to right, top to bottom”.

def unique_paths_with_obstacles(grid):
    """Count paths from top-left to bottom-right moving only right or down.
    grid[r][c] == 1 marks an obstacle. dp[c] rolls one row at a time.
    Time O(rows*cols), space O(cols)."""
    if not grid or grid[0][0] == 1:
        return 0
    cols = len(grid[0])
    dp = [0] * cols
    dp[0] = 1                                   # one way to be at the start
    for row in grid:
        for c in range(cols):
            if row[c] == 1:
                dp[c] = 0                       # unreachable cell
            elif c > 0:
                dp[c] += dp[c - 1]              # from above (dp[c]) + from left (dp[c-1])
    return dp[cols - 1]


def min_path_sum(grid):
    """Minimum sum of values along a right/down path from corner to corner.
    Same state, min instead of sum. Time O(rows*cols), space O(cols)."""
    rows, cols = len(grid), len(grid[0])
    dp = [float("inf")] * cols
    dp[0] = 0
    for r in range(rows):
        for c in range(cols):
            if c == 0:
                dp[c] = dp[c] + grid[r][c]              # only from above
            else:
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]
    return dp[cols - 1]


assert unique_paths_with_obstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]]) == 2
assert min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]) == 7   # 1→3→1→1→1

The rolling trick works because when we are about to write dp[c] for row r, the array still holds row r-1 at position c (the value “from above”) and already holds row r at position c-1 (the value “from the left”). That single array is doing double duty, and understanding why it is correct is the same insight that makes the 1D knapsack loop run backwards.

Space optimization with rolling arrays

If dp[i][*] depends only on dp[i-1][*], you never need more than two rows — and often just one, if you iterate in the right direction. The rule:

0/1 knapsack is the first row of that table (descending, each item once). Unbounded knapsack and the coin-change count are the second (ascending, items reusable). This is exactly why the two loop directions produce different problems and why “just reverse the loop” is a real, precise transformation rather than a trick.

The cost of the optimization is that you destroy the information needed for reconstruction. Which brings us to:

Reconstructing the solution, not just its value

Most DP write-ups stop at the number. Interviews and real applications almost always want the actual answer: which items, which subsequence, which edits. Two techniques:

A. Keep the full table and walk backwards, re-deriving at each cell which choice produced the stored value.

def lcs_string(a, b):
    """Return the actual LCS, not just its length.
    Build the full table, then walk from (n, m) back to (0, 0):
    a diagonal step means the characters were matched and belong to the answer.
    Time O(n*m), space O(n*m). Walk-back is O(n+m)."""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 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])

    out = []
    i, j = n, m
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])           # this pair was matched
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1                         # value came from dropping a[i-1]
        else:
            j -= 1                         # value came from dropping b[j-1]
    return "".join(reversed(out))


assert lcs_string("ABCBDAB", "BDCABA") == "BCBA"

B. Store a parent/choice pointer alongside the value. Costs an extra table but makes the walk-back trivial and works when re-deriving the choice is awkward.

def knapsack_items(weights, values, capacity):
    """Return (best_value, chosen_indices). `take[i][w]` records whether item i
    was used in the optimum for capacity w. Time O(n*W), space O(n*W)."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    take = [[False] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]
            if wi <= w and vi + dp[i - 1][w - wi] > dp[i][w]:
                dp[i][w] = vi + dp[i - 1][w - wi]
                take[i][w] = True

    chosen, w = [], capacity
    for i in range(n, 0, -1):
        if take[i][w]:
            chosen.append(i - 1)
            w -= weights[i - 1]
    return dp[n][capacity], sorted(chosen)


assert knapsack_items([1, 3, 4, 5], [1, 4, 5, 7], 7) == (9, [1, 2])

The trade-off is unavoidable: you cannot both roll the array down to O(W) and reconstruct naively. If memory forces the rolling array and you still need the path, the standard fix is Hirschberg’s algorithm — divide and conquer on the sequence, computing the optimal crossing point of the midline with linear space and recursing on both halves. It gives O(n·m) time and O(min(n,m)) space with full reconstruction, and it is what real diff implementations use.

How to recognize a DP problem

The signals, roughly in order of reliability:

1. The question asks for a count, a maximum, a minimum, or “is it possible” over a combinatorial space — “how many ways”, “the longest”, “the cheapest”, “can you reach”. If it asks you to list all solutions instead, that is backtracking, not DP.
2. Choices at each step, and choosing greedily is provably wrong. You found a counterexample to the greedy (like [1,3,4] for amount 6). That counterexample is the evidence that you must explore all choices — and DP is how you afford to.
3. Your brute-force recursion is exponential, but its arguments repeat. Write the brute force first, draw two levels of the recursion tree, and look for a duplicated call. If you see one, add a cache and you are done.
4. The input constraints hint at the table size. n ≤ 20 suggests bitmask DP over subsets (O(2ⁿ·n)). n ≤ 100 with a second dimension suggests O(n²) or O(n³). n ≤ 10⁵ rules out anything two-dimensional in n and points at O(n log n) — an LIS-style structure, not a table. Constraint sizes in a well-posed problem are a hint about the intended complexity, and complexity determines the shape of the state.
5. The state is small and describable in a sentence. If you cannot say what dp[i][j] means in one English sentence, you do not have a DP formulation yet — you have a table and some loops, and it will be wrong.

Conversely, if subproblems are disjoint it is divide and conquer; if a single local rule is provably optimal it is greedy; if you need every solution enumerated it is backtracking; and if the subproblems interfere (longest simple path, most scheduling with arbitrary constraints) there may be no polynomial algorithm at all.

Complexity summary

Two entries above are worth naming even though they are beyond the roadmap node: interval DP (state is a range [i, j], transition splits at every k inside it — matrix chain multiplication, optimal BST, burst balloons) and bitmask DP (state includes a subset encoded in an integer — travelling salesman, assignment problems). Both are just the same four questions answered with a different state; recognizing them is mostly a matter of having seen one.

Best Practices

• Write the brute-force recursion first, then add a cache. Do not attempt to write the bottom-up table straight away. The recursion is where the thinking happens; memoizing it is a one-line mechanical step; converting to bottom-up afterwards is another mechanical step. Starting from the table means designing the state and the loop order simultaneously, and you will get both wrong.
• Say out loud what dp[i][j] means before writing any loop. One English sentence, with the boundaries pinned down (“dp[i][j] is the LCS of the first i characters of a and the first j of b” — not “of a[i] and b[j]”). Most DP bugs are state-definition bugs wearing an off-by-one costume.
• Count states × transitions before implementing. That product is your complexity. If it exceeds roughly 10⁸ simple operations, redesign the state — do not implement and hope.
• Get the base cases right and test them explicitly. Empty string, zero capacity, n = 0, n = 1. These are where the off-by-ones live, and a table that is right in the middle and wrong at the edges is much harder to debug than one that is wrong everywhere.
• Optimize space last, and only when it matters. The rolling array makes the code harder to read and destroys reconstruction. O(n·m) on a 1000×1000 problem is a million cells — fine. Roll it when the memory bound is real, not reflexively.
• Watch the loop direction like a hawk. Descending means “previous row, each item once”; ascending means “current row, items reusable”. These are different problems, both compile, and both look plausible.
• In Python, prefer bottom-up for anything with depth over a few thousand. RecursionError on a deep memoized recursion is a real production failure and sys.setrecursionlimit is not a fix — a too-high limit crashes the interpreter’s C stack rather than raising cleanly.
• Do not use @lru_cache on a function that closes over mutable problem state. The cache outlives the call, and the second test case gets the first one’s answers. If you do use it, clear it (f.cache_clear()) between problem instances, or pass the state as a hashable argument.
• Beware pseudo-polynomial complexity. O(n·W) looks polynomial and is not. Check the magnitude of W (or the amount, or the target sum) against the input constraints before committing to the approach.
• When the answer must be reconstructed, decide that before optimizing. Keep the full table, or keep a parent-pointer table, or plan for Hirschberg’s algorithm. Retrofitting reconstruction onto a rolled array means rewriting.
• Verify against the brute force on small random inputs. A 20-line random tester comparing the DP with an exhaustive search on inputs of size ≤ 10 catches essentially every DP bug in a couple of seconds, and is far faster than staring at the recurrence.

References

• roadmap.sh — Data Structures & Algorithms
• Dynamic programming — Wikipedia
• Bellman equation — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 15: Dynamic Programming
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• cp-algorithms — Longest Increasing Subsequence
• cp-algorithms — Knapsack problem
• cp-algorithms — Edit distance
• Knapsack problem — Wikipedia
• Longest common subsequence — Wikipedia
• Levenshtein distance — Wikipedia
• Hirschberg’s algorithm — Wikipedia
• Python Documentation — functools.lru_cache
• Python Documentation — bisect