DP Problem Walkthroughs: Make One, Knapsack, Edit Distance, LIS and Partition With Reconstruction

By 0xmote · May 25, 2026 · 19 min read · Updated Sep 27, 2026 Advanced Tutorial

Key takeaways

Six classic DP problems solved the same way every time: define the state in one sentence, derive the transition, fix the base cases, pick a loop order that only reads finished cells, then walk the table backward to recover the actual answer. Each walkthrough ends with the bug that most often fails a submission, and shows what space optimization costs you when the problem asks for the path, items or edit operations.

Introduction

This article is the practice companion to Dynamic Programming: Memoization vs Tabulation, which explains when DP applies, and DP Patterns, which catalogues the recurring shapes (knapsack, LCS, LIS, grid paths). Here the focus is on working specific problems through to the end, including the part many solutions stop short of: recovering which choices produced the optimal value.

Every walkthrough uses the same five questions:

State. What does one cell mean? Write it as a sentence: “dp[i] is the minimum number of operations to turn i into 1.”
Transition. Which smaller states can the last decision come from?
Base cases. Which cells are known without a decision?
Order. In what order must cells be filled so that every cell reads only finished cells?
Reconstruction. How do you walk back from the answer cell to the decisions?

If you cannot write the sentence in step 1, you are not ready to write code. Most wrong DP submissions I have seen, my own included, come from a state definition that was never written down and shifted meaning halfway through the loop.

Make One (Baekjoon 1463)

Problem: from an integer n, reach 1 using “divide by 3 if divisible”, “divide by 2 if divisible” or “subtract 1”. Minimize the number of operations.

Why not greedy

Dividing by 3 whenever possible is the obvious greedy, and it is wrong:

def make_one_greedy(n):
    steps = 0
    while n > 1:
        if n % 3 == 0:
            n //= 3
        elif n % 2 == 0:
            n //= 2
        else:
            n -= 1
        steps += 1
    return steps

print(make_one_greedy(10))  # 4: 10 -> 5 -> 4 -> 2 -> 1

The optimum is 10 -> 9 -> 3 -> 1, three steps. Subtracting 1 looks like the weakest move but sets up a division by 3. Whenever a cheap move now can enable a much better move later, you need to evaluate every option, which is what DP does. The general version of this argument is in Greedy Algorithms.

The walkthrough

State: dp[i] = minimum operations to turn i into 1.
Transition: the first operation from i goes to i - 1, i // 2 or i // 3, so dp[i] = 1 + min(dp[i-1], dp[i//2] if i%2==0, dp[i//3] if i%3==0).
Base: dp[1] = 0.
Order: every transition goes to a smaller number, so fill i = 2, 3, ..., n.
Reconstruction: record which move won in parent[i] and follow it from n.

def make_one(n):
    dp = [0] * (n + 1)
    parent = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i], parent[i] = dp[i - 1] + 1, i - 1
        if i % 2 == 0 and dp[i // 2] + 1 < dp[i]:
            dp[i], parent[i] = dp[i // 2] + 1, i // 2
        if i % 3 == 0 and dp[i // 3] + 1 < dp[i]:
            dp[i], parent[i] = dp[i // 3] + 1, i // 3
    path = [n]
    while path[-1] != 1:
        path.append(parent[path[-1]])
    return dp[n], path

print(make_one(10))   # (3, [10, 9, 3, 1])
print(make_one(1))    # (0, [1])
print(make_one(642))  # (10, [642, 321, 320, 160, 80, 40, 20, 10, 9, 3, 1])

Storing the decision is cheaper than recomputing it on the way back, and it guarantees the path you print is the one the table actually chose.

The bug that fails submissions: recursion depth

The top-down version is the same recurrence with lru_cache, and it works on the sample. The problem allows n up to 10^6:

from functools import lru_cache

@lru_cache(maxsize=None)
def make_one_memo(n):
    if n == 1:
        return 0
    r = make_one_memo(n - 1) + 1
    if n % 2 == 0:
        r = min(r, make_one_memo(n // 2) + 1)
    if n % 3 == 0:
        r = min(r, make_one_memo(n // 3) + 1)
    return r

try:
    print(make_one_memo(5000))
except RecursionError:
    print("RecursionError")  # printed

The n - 1 branch is evaluated first and recurses all the way down before anything is cached, so the depth is about n. CPython’s default limit is 1000 frames. The bottom-up table has no such problem and handles 10^6 directly.

0/1 Knapsack With the Chosen Items (Baekjoon 12865)

Problem: items have weight and value; the bag holds weight W. Maximize total value, each item used at most once. The sample from 12865: weights [6, 4, 3, 5], values [13, 8, 6, 12], W = 7, answer 14.

State: dp[i][w] = best value using only the first i items with capacity w.
Transition: item i is either skipped (dp[i-1][w]) or taken (dp[i-1][w - wt] + val, only if wt <= w).
Base: dp[0][w] = 0 for all w: no items, no value.
Order: row i reads only row i - 1, so fill row by row.
Reconstruction: walk i from n down to 1. If dp[i][w] != dp[i-1][w], item i must have been taken, so record it and subtract its weight.

def knapsack_items(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wt <= w and dp[i - 1][w - wt] + val > dp[i][w]:
                dp[i][w] = dp[i - 1][w - wt] + val
    chosen, w = [], W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            chosen.append(i - 1)
            w -= weights[i - 1]
    return dp[n][W], chosen[::-1], dp

weights = [6, 4, 3, 5]
values = [13, 8, 6, 12]
best, items, dp = knapsack_items(weights, values, 7)
print(best, items)  # 14 [1, 2]
for row in dp:
    print(row)
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 13, 13]
# [0, 0, 0, 0, 8, 8, 13, 13]
# [0, 0, 0, 6, 8, 8, 13, 14]
# [0, 0, 0, 6, 8, 12, 13, 14]

Reading the backtrack: dp[4][7] == dp[3][7] == 14, so item 3 (weight 5) was not needed. dp[3][7] = 14 != dp[2][7] = 13, so item 2 (weight 3) was taken; capacity drops to 4. dp[2][4] = 8 != dp[1][4] = 0, so item 1 (weight 4) was taken; capacity drops to 0. Items 1 and 2, value 8 + 6.

Space optimization, and what it costs

Because row i reads only row i - 1, a single array updated from high w to low w gives the same value in O(W) memory:

def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):   # descending: dp[w - wt] is still the old row
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp

def knapsack_1d_forward(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(wt, W + 1):       # ascending: dp[w - wt] already includes this item
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

print(knapsack_1d(weights, values, 7)[7])  # 14
print(knapsack_1d_forward([3], [5], 7))    # 10: the single item was used twice

The ascending loop is the most common knapsack bug: it silently solves the unbounded version. It even gives the right answer on the 12865 sample (14), which is why it survives local testing.

The bigger cost is reconstruction. After the 1D loop, dp only holds the last row; the comparison dp[i][w] != dp[i-1][w] is gone. If the problem asks for the items, keep the decisions separately. A boolean table is much smaller in practice than a table of values, and the value array can still be 1D:

def knapsack_1d_with_items(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    took = [[False] * (W + 1) for _ in range(n)]
    for i, (wt, val) in enumerate(zip(weights, values)):
        for w in range(W, wt - 1, -1):
            if dp[w - wt] + val > dp[w]:
                dp[w] = dp[w - wt] + val
                took[i][w] = True
    chosen, w = [], W
    for i in range(n - 1, -1, -1):
        if took[i][w]:
            chosen.append(i)
            w -= weights[i]
    return dp[W], chosen[::-1]

print(knapsack_1d_with_items(weights, values, 7))  # (14, [1, 2])

took[i][w] records whether item i improved capacity w at the moment it was processed, which is exactly the information the 2D comparison used. I checked this against the 2D version on 500 random small instances before trusting it; the point of that habit is in section 6.

Edit Distance With the Edit Script (LeetCode 72)

Problem: the minimum number of single-character inserts, deletes and replacements to turn s1 into s2, and the operations themselves.

State: dp[i][j] = edits to turn the first i characters of s1 into the first j of s2.
Transition: if s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1]. Otherwise 1 + min(delete dp[i-1][j], insert dp[i][j-1], replace dp[i-1][j-1]).
Base: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).
Order: row by row, left to right; each cell reads up, left and up-left.
Reconstruction: from (m, n), find which neighbor produced the value and step there.

def edit_script(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete s1[i-1]
                                   dp[i][j - 1],      # insert s2[j-1]
                                   dp[i - 1][j - 1])  # replace
    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and s1[i - 1] == s2[j - 1]:
            i, j = i - 1, j - 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f"replace {s1[i - 1]!r} with {s2[j - 1]!r}")
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f"delete {s1[i - 1]!r}")
            i -= 1
        else:
            ops.append(f"insert {s2[j - 1]!r}")
            j -= 1
    return dp[m][n], ops[::-1]

print(edit_script("horse", "ros"))
# (3, ["replace 'h' with 'r'", "delete 'r'", "delete 'e'"])
print(edit_script("abc", ""))
# (3, ["delete 'a'", "delete 'b'", "delete 'c'"])

Applying the first script: “horse” -> “rorse” -> “rose” -> “ros”. Note the loop condition is i > 0 or j > 0, not and: when one string is exhausted, the remaining characters of the other still need deletes or inserts. With and, the "abc", "" case would return no operations.

Optimal scripts are usually not unique. For “intention” to “execution” this backtrack prefers replacements and returns five of them, while LeetCode’s explanation shows a delete, three replacements and an insert. Both cost 5. If a problem asks for a specific script (lexicographically smallest, fewest replacements), the tie-break order in the backtrack has to encode that rule.

Two rows and the base-case trap

Each row reads only the previous one, so two rows are enough for the distance:

def edit_distance_two_rows(s1, s2):
    if len(s1) < len(s2):
        s1, s2 = s2, s1          # keep the row as short as possible
    prev = list(range(len(s2) + 1))
    for i in range(1, len(s1) + 1):
        cur = [i] + [0] * len(s2)   # cur[0] = i is the dp[i][0] base case
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]

print(edit_distance_two_rows("horse", "ros"))  # 3

As with knapsack, two rows cannot produce the script. Hirschberg’s algorithm recovers an optimal alignment in linear space by splitting the problem at the middle row recursively, at roughly twice the time; it is worth knowing it exists for problems with long strings and a memory limit.

The base-case bug is forgetting cur[0] = i (or the dp[i][0] = i loop in the 2D version). A table that starts at zero claims you can turn “abc” into "" for free, and the error spreads through every cell: on “horse” and “ros” that version returns 2.

LIS, Including the Subsequence (LeetCode 300)

The O(n log n) method keeps, for each length k, the smallest value that can end an increasing subsequence of length k + 1. DP Patterns explains why that array is not itself an LIS. To recover an actual subsequence, store indices instead of values and give each element a parent: the element that ended the run it extended.

from bisect import bisect_left

def lis_sequence(arr):
    tail_vals, tail_idx = [], []
    parent = [-1] * len(arr)
    for i, x in enumerate(arr):
        k = bisect_left(tail_vals, x)
        if k > 0:
            parent[i] = tail_idx[k - 1]   # x extends the best run of length k
        if k == len(tail_vals):
            tail_vals.append(x)
            tail_idx.append(i)
        else:
            tail_vals[k] = x
            tail_idx[k] = i
    seq, i = [], tail_idx[-1] if tail_idx else -1
    while i != -1:
        seq.append(arr[i])
        i = parent[i]
    return seq[::-1], tail_vals

print(lis_sequence([10, 9, 2, 5, 3, 7, 101, 18]))  # ([2, 3, 7, 18], [2, 3, 7, 18])
print(lis_sequence([3, 4, 5, 1]))                  # ([3, 4, 5], [1, 4, 5])
print(lis_sequence([]))                            # ([], [])

The second example shows why the parent links matter: tail_vals ends as [1, 4, 5], which is not a subsequence of the input at all, but following parents from the last tail recovers [3, 4, 5]. The parent is recorded at insertion time, when tail_idx[k - 1] really was the end of a length-k run before x; later overwrites of tail_idx do not change it. The binary search on tail_vals is the lower-bound search from Binary Search.

The strict versus non-strict distinction lives in one function name:

from bisect import bisect_right

def lnds_len(arr):
    tails = []
    for x in arr:
        k = bisect_right(tails, x)   # equal values may extend
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)

print(len(lis_sequence([2, 2, 2])[0]), lnds_len([2, 2, 2]))  # 1 3
print(lnds_len([1, 3, 3, 2, 3]))                             # 4

Problems phrased as “longest non-decreasing”, “minimum number of strictly decreasing piles” or box-stacking variants hinge on this choice, and the samples rarely include equal values.

Partition Equal Subset Sum (LeetCode 416)

Problem: can the array be split into two parts with equal sums? Equivalently, is there a subset summing to total / 2?

State: dp[s] = some subset of the items seen so far sums to s.
Transition: for each item x, dp[s] = dp[s] or dp[s - x].
Base: dp[0] = True (the empty subset).
Order: this is 0/1 knapsack with booleans, so s must descend.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

def can_partition_forward(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for s in range(x, target + 1):   # bug: lets x be reused
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

for nums in ([1, 5, 11, 5], [1, 2, 3, 5], [1, 2, 5]):
    print(nums, can_partition(nums), can_partition_forward(nums))
# [1, 5, 11, 5] True True
# [1, 2, 3, 5] False False
# [1, 2, 5] False True

The forward loop agrees with the correct one on both LeetCode samples and is wrong on [1, 2, 5]: it builds 4 as 1 + 1 + 1 + 1. This is the same ascending-loop bug as the knapsack section, and a three-element input is enough to expose it.

In Python there is also a compact version using an integer as a bitset, where bit s means “sum s is reachable”. Shifting by x adds x to every reachable sum at once, and because the shift reads the old value of bits, each item is used once:

def can_partition_bits(nums):
    total = sum(nums)
    if total % 2:
        return False
    bits = 1
    for x in nums:
        bits |= bits << x
    return (bits >> (total // 2)) & 1 == 1

print(can_partition_bits([1, 5, 11, 5]), can_partition_bits([1, 2, 5]))  # True False

It does the same O(n x target) work, but in machine-word chunks inside CPython’s big-integer code rather than one Python-level operation per cell.

Interval DP: Longest Palindromic Subsequence (LeetCode 516)

Problem: the length of the longest subsequence of s that reads the same both ways.

State: dp[i][j] = answer for the substring s[i..j], inclusive.
Transition: if s[i] == s[j], both ends join the inner answer: dp[i+1][j-1] + 2. Otherwise drop one end: max(dp[i+1][j], dp[i][j-1]).
Base: dp[i][i] = 1. Empty ranges (i > j) are 0.
Order: dp[i][j] reads row i + 1, so rows must be filled from the bottom up: i from n - 1 down to 0, and j from i + 1 up.

def longest_palindrome_subseq(s):
    n = len(s)
    if n == 0:
        return 0
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

def lps_wrong_order(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):                   # top-down rows: row i+1 is still empty
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

print(longest_palindrome_subseq("bbbab"), longest_palindrome_subseq("character"))  # 4 5
print(lps_wrong_order("bbbab"), lps_wrong_order("character"))                      # 2 2

When j == i + 1 and the two characters match, dp[i+1][j-1] is dp[i+1][i], an empty range that stays 0 in the lower triangle, so the answer is correctly 2. The wrong-order version runs without an error and returns small, plausible numbers, which is the worst kind of failure. Iterating over substring length (1, 2, 3, …) instead of over i is an equally valid order, and it generalizes to interval problems like matrix-chain multiplication where the split point sits in the middle.

This is the loop-order bug I find hardest to spot by reading, because the recurrence on the page is correct. What catches it for me is asking, for one specific cell, “which cells does this read, and have they been written yet?” If I cannot answer that from the loop headers alone, I change the order until I can.

How to Check a DP You Are Not Sure Of

Several bugs above (ascending knapsack loops, missing base cases, wrong fill order) pass the samples. A brute-force comparison on small random inputs catches them in seconds. For partition, the brute force is “try every subset”:

import random
from itertools import combinations

def brute_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    return any(sum(c) == total // 2
               for r in range(len(nums) + 1)
               for c in combinations(nums, r))

rng = random.Random(0)
for _ in range(1000):
    nums = [rng.randint(1, 9) for _ in range(rng.randint(1, 6))]
    if can_partition_forward(nums) != brute_partition(nums):
        print("counterexample:", nums)
        break
else:
    print("no counterexample")

Running this against can_partition prints no counterexample; against can_partition_forward it stops at the first input where an item gets reused. When reconstruction is involved, also check that the recovered answer is valid on its own terms (items fit and sum to the reported value, the LIS is increasing and is a subsequence, applying the edit script produces s2), not just that the number matches.

State, order and the bug that fails each problem

Problem	State	Order	Reconstruction	Typical failing bug
Make One	`dp[i]`: ops from `i` to 1	`i` ascending	`parent[i]`	Recursive memo hits the recursion limit
0/1 knapsack	`dp[i][w]`: best value, first `i` items	Row by row; 1D needs `w` descending	Compare rows, or keep `took[i][w]`	Ascending 1D loop reuses items
Edit distance	`dp[i][j]`: prefix to prefix	Row by row	Step to the neighbor that produced the value	Missing `dp[i][0]`, `dp[0][j]` bases
LIS (n log n)	Smallest tail per length	Left to right	Parent index at insertion	`bisect_left` vs `bisect_right`
Partition	`dp[s]`: sum reachable	`s` descending	(keep `took` if needed)	Ascending loop reuses items
Palindromic subsequence	`dp[i][j]`: substring answer	`i` descending	Walk ends inward	Filling rows top-down