Dynamic Programming LeetCode Pattern Guide — Knapsack, LIS, and Interval DP Templates

A dynamic programming LeetCode pattern guide is useful only if it helps you recognize the state, recurrence, and iteration order under interview pressure. Knapsack, LIS, and interval DP look different on the surface, but the work is the same: define what a subproblem means, decide how choices transition between subproblems, and compute answers in an order where dependencies already exist.

This guide gives practical templates, recognition rules, and interview narration for the DP patterns that show up most often.

Dynamic programming LeetCode pattern guide: what DP is really testing

Dynamic programming is not a bag of memorized formulas. It is a way to avoid recomputing overlapping subproblems when a problem has optimal substructure. In interviews, DP tests whether you can turn a vague recursive idea into a precise state definition.

The four questions to ask every time:

1. What does dp[...] mean? State definition must be exact.
2. What choice am I making? Pick, skip, split, extend, merge, buy, sell, include, exclude.
3. What smaller states does this depend on? That gives the recurrence.
4. What order computes dependencies first? Top-down memoization or bottom-up tabulation.

If you are stuck, write a brute-force recursion first. DP often appears when the recursion repeats the same (index, remaining_capacity) or (left, right) state many times.

A strong interview line: "I'll define the state before optimizing space. If the state is wrong, the optimized code is just a faster wrong answer."

Pattern recognition cheat sheet

| Pattern | Clues in prompt | Typical state | Common examples | |---|---|---|---| | 0/1 knapsack | choose each item once, capacity/budget/target | dp[i][cap] or dp[cap] | subset sum, partition equal subset, target sum | | Unbounded knapsack | can reuse item multiple times | dp[amount] | coin change, combination sum variants | | LIS | longest increasing/valid subsequence | dp[i] or tails array | LIS, Russian doll envelopes, divisible subset | | Interval DP | choose split inside range | dp[l][r] | burst balloons, matrix chain, palindrome partition | | Grid DP | paths through matrix | dp[r][c] | unique paths, min path sum | | String DP | prefixes of strings | dp[i][j] | edit distance, LCS, regex matching | | State machine DP | limited actions over time | dp[day][state] | stock buy/sell, cooldown, transaction limit |

The fastest way to improve is to classify the problem before coding. Ask: is the constraint an index, a capacity, a pair of boundaries, or a state machine? That usually reveals the DP dimensions.

0/1 knapsack template

Use 0/1 knapsack when each item can be used at most once and you are optimizing or checking against a capacity, target, or budget.

State:

dp[i][cap] = best value using first i items with capacity cap

Transition:

• skip item i: dp[i-1][cap]
• take item i if it fits: dp[i-1][cap-weight[i]] + value[i]

Template:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w = weights[i - 1]
        v = values[i - 1]
        for cap in range(capacity + 1):
            dp[i][cap] = dp[i - 1][cap]
            if cap >= w:
                dp[i][cap] = max(dp[i][cap], dp[i - 1][cap - w] + v)
    return dp[n][capacity]

Space-optimized 0/1 version:

dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
    for cap in range(capacity, w - 1, -1):
        dp[cap] = max(dp[cap], dp[cap - w] + v)

The reverse loop is the key. It prevents using the same item multiple times in one iteration. If you loop forward, you accidentally turn 0/1 knapsack into unbounded knapsack.

How to narrate it: "For each item, I decide whether to take or skip it. Because each item can be used once, the one-dimensional version must iterate capacity backward."

Subset sum and partition as knapsack

Many interviewers disguise knapsack as a boolean problem.

For Partition Equal Subset Sum, the question is whether some subset reaches sum(nums) / 2.

State:

dp[t] = whether we can make target t using numbers seen so far

Template:

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for x in nums:
        for t in range(target, x - 1, -1):
            dp[t] = dp[t] or dp[t - x]
    return dp[target]

For Target Sum, the trick is algebra: assigning plus/minus signs can become finding a subset with a derived sum. But do not force the trick too early. In an interview, first explain the direct state dp[i][current_sum], then optimize if the constraints require it.

Common traps:

• forgetting dp[0] = True
• using forward iteration for 0/1 choices
• ignoring negative sums in target-sum variants
• optimizing space before proving the recurrence

Unbounded knapsack and coin change

Unbounded knapsack appears when you can reuse items: coin denominations, unlimited pieces, repeated actions.

Minimum coins:

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if a >= c:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

Counting combinations, not permutations:

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

The loop order changes the meaning. Coins outside and amount inside counts combinations because each coin enters in a fixed order. Amount outside and coins inside often counts permutations. In interviews, say what you are counting before writing loops.

LIS: O(n²) DP template

Longest Increasing Subsequence is the classic "best ending at i" pattern.

State:

dp[i] = length of the longest increasing subsequence ending at index i

Transition:

For all j < i, if nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1).

Template:

def length_of_lis(nums):
    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)

This pattern adapts to:

• largest divisible subset: replace < with divisibility and reconstruct parents
• longest string chain: sort words by length and transition from predecessor words
• Russian doll envelopes: sort one dimension and run LIS on the other with careful tie handling
• maximum sum increasing subsequence: store best sum ending at i, not length

The interview narration: "I am not saying the global best ends at i; I am defining a local best that gives me clean transitions. The answer is the max over all endings."

LIS: O(n log n) tails template

The faster LIS solution keeps tails[k] as the smallest possible tail value of an increasing subsequence of length k + 1. It does not directly store a valid final sequence unless you add parent tracking, but it gives the length efficiently.

from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Use bisect_left for strictly increasing. Use bisect_right when equal values are allowed in a non-decreasing variant. The subtlety in envelope problems is sorting widths ascending and heights descending for equal widths so equal-width envelopes do not chain.

Do not jump to this version if you cannot explain it. In many interviews, the O(n²) DP with correct reasoning is enough unless constraints demand more.

Interval DP template

Interval DP appears when the optimal answer for a range depends on choosing a split point or a final action inside that range. The state usually looks like dp[l][r].

Clues:

• "minimum cost to merge"
• "burst/remove elements"
• "best score from subarray"
• "palindrome partition"
• "matrix chain multiplication"
• choices combine left and right subproblems

Generic template:

n = len(arr)
dp = [[0] * n for _ in range(n)]

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        dp[l][r] = float('inf')  # or 0 for max problems
        for k in range(l, r):
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + cost(l, k, r))

For Burst Balloons, the trick is choosing the last balloon burst in the interval, not the first. Add virtual 1s at both ends. Then:

dp[l][r] = max coins from bursting balloons strictly between l and r

def max_coins(nums):
    nums = [1] + [x for x in nums if x > 0] + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]

    for gap in range(2, n):
        for l in range(0, n - gap):
            r = l + gap
            for k in range(l + 1, r):
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + nums[l] * nums[k] * nums[r])
    return dp[0][n - 1]

The phrase to remember: "If choosing first makes the neighbors unstable, try choosing last." That insight unlocks many interval problems.

Top-down vs bottom-up

Top-down memoization is usually faster to write and easier to reason about. Bottom-up tabulation is often easier to optimize and avoids recursion depth.

Use top-down when:

• state graph is sparse
• recurrence is natural recursively
• you are still discovering the state
• constraints allow recursion

Use bottom-up when:

• you need strict O(n²) or O(n * target) performance
• recursion depth is risky
• iteration order is obvious
• you want space optimization

Interview move: start top-down to prove correctness, then convert to bottom-up if needed. That is better than forcing a table before you understand dependencies.

How to talk through DP in an interview

A clean explanation is often the difference between a correct-looking solution and a hire signal. Use this sequence:

1. Start with brute force. "At each index I can choose or skip, which creates repeated subproblems."
2. Name the repeated state. "The only information that matters is index and remaining target."
3. Define dp in plain English. Do this before code.
4. Write the recurrence verbally. "If I skip, I keep the old best; if I take, I add value and reduce capacity."
5. State base cases. Empty prefix, target zero, single-element interval, or impossible state.
6. Choose memo or table. Explain why the dependencies are safe.
7. Give complexity. Include both time and space, then mention if a one-dimensional optimization is valid.

Avoid saying "this is just DP" as if the interviewer should fill in the proof. The proof is the state definition plus recurrence. If you can say those clearly, even a minor syntax bug is less damaging.

Mini scorecard for recognizing the right pattern

When you read a new problem, score it quickly:

• Does it ask for best/count/possible over choices? DP is likely.
• Is each item used once? Think 0/1 knapsack.
• Can items repeat? Think unbounded knapsack.
• Does order matter but elements can be skipped? Think subsequence or LIS.
• Does choosing something split a range into left and right parts? Think interval DP.
• Are there two strings or arrays being aligned? Think prefix DP.
• Are there a few modes over time, such as holding/not holding stock? Think state-machine DP.

This scorecard keeps you from reaching for the wrong template. Most hard DP problems are hard because the first state you imagine is missing one piece of information. Add the missing information deliberately, then simplify only after the recurrence works.

DP debugging checklist

Before you submit, check:

• What does each state mean in one sentence?
• Are base cases initialized correctly?
• Does the recurrence use only smaller or already-computed states?
• Are loops in the right direction for 0/1 vs unbounded choices?
• Are equality rules correct: <, <=, bisect_left, bisect_right?
• Is the answer dp[n], max(dp), dp[0][n-1], or something else?
• Did you handle empty input and single-element input?
• Are you using impossible sentinels safely, such as inf or -inf?
• Can you reconstruct a solution if the prompt asks for the actual subset or sequence?

DP gets easier when you stop asking "which formula is this?" and start asking "what information must the future know about the past?" Knapsack needs remaining capacity or target. LIS needs the previous ending. Interval DP needs boundaries. Once you identify the information, the table shape follows.

Related guides

• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Greedy Algorithms LeetCode Pattern Guide — Interval Scheduling and Exchange Arguments — A practical greedy algorithms LeetCode pattern guide for recognizing interval scheduling, proving choices with exchange arguments, and avoiding the traps that make greedy solutions fail.
• Sliding Window LeetCode Pattern Guide — Fixed and Variable Window Templates — A template-driven guide to fixed and variable sliding window problems, covering invariants, frequency maps, at-most-K counting, replacement tricks, deques, and common traps.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.