Skip to content
Data Structures & Algorithms

Dynamic Programming interview questions and answers

35 questions, 27 with code. About 2 h 56 min to read them all.

By TestLab · Updated

Plan for an interview
35 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

How does dynamic programming differ from plain recursion?

Dynamic programming solves a problem by reusing results from overlapping subproblems, while plain recursion may solve the same subproblem repeatedly. DP usually adds memoization or organizes computation in an order that stores each required result once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For a problem such as computing Fibonacci numbers, define the state clearly:

  • dp[i] means the value of the ith Fibonacci number.

  • Recurrence: dp[i] = dp[i - 1] + dp[i - 2].

  • Base cases: dp[0] = 0 and dp[1] = 1.

  • Computation order: Calculate states from smaller indices to larger indices.

Dynamic programming requires two properties:

  • Overlapping subproblems: Different branches of the computation request the same states. For example, plain recursive Fibonacci repeatedly calculates fib(3) and fib(2).

  • Optimal substructure: A state’s answer can be constructed from answers to smaller states using the recurrence.

Difference from Recursion

Recursion and dynamic programming are not mutually exclusive. Recursion describes the control flow; DP describes how previously calculated states are reused.

For the Fibonacci example:

Approach Time Space When to use
Plain recursion O(2^n) O(n) Small inputs or as a baseline when repeated-state reuse is unnecessary
Top-down DP with memoization O(n) O(n) When dependencies are discovered naturally
Bottom-up DP O(n) O(n) When dependencies can be calculated in order
Bottom-up with rolling variables O(n) O(1) When only the previous two states are needed

For plain recursive Fibonacci, the time is O(2^n) in the best, average, and worst cases because the recursion tree contains exponentially many calls. Its space is O(n) because the maximum recursion depth is O(n).

Memoized and table-based bottom-up Fibonacci both take O(n) time in all cases. Their space is O(n) because they retain O(n) states; retaining only the previous two states reduces auxiliary space to O(1). These complexities include the recursion stack where applicable but do not count the input itself.

Filled DP Table

For n = 5:

i dp[i] Calculation
0 0 Base case
1 1 Base case
2 1 1 + 0
3 2 1 + 1
4 3 2 + 1
5 5 3 + 2

The table demonstrates why each state is calculated only once.

Common Pitfalls

  • Undefined state: Always specify exactly what dp[i] or dp[i][j] represents.

  • Incorrect base cases: They must cover every state that the recurrence cannot calculate.

  • Wrong computation order: Bottom-up dependencies must already be available.

  • Recursion depth: Top-down Fibonacci approaches Python’s default recursion limit for large n; use an iterative version or an explicit stack.

  • Unnecessary storage: If only a fixed number of previous states are needed, retain only those values.

  • Invalid input: A Fibonacci implementation should reject negative n and handle n = 0 and n = 1. Duplicates, sorted input, disconnected graphs, and cycles are not applicable to this problem.

  • Integer overflow in other languages: Use a sufficiently large integer type for large results.

Interview Tips

Expect follow-up questions about choosing a suitable state, proving that the recurrence is correct, identifying overlapping subproblems and optimal substructure, selecting a computation order, and reducing space usage. Explain these points before discussing implementation details.

2

What are overlapping subproblems in dynamic programming?

Overlapping subproblems occur when a recursive algorithm repeatedly solves the same smaller subproblems instead of computing each unique subproblem only once. This property is one of the two hallmarks (along with optimal substructure) that make a problem suitable for dynamic programming. By storing results of subproblems the first time they are computed, dynamic programming avoids redundant work and reduces exponential time complexity to polynomial time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition

A problem has overlapping subproblems if its recursive decomposition generates identical subproblems multiple times. For example, computing the nth Fibonacci number recursively requires fib(n-1) and fib(n-2), but fib(n-2) is also needed inside fib(n-1), so it gets computed twice. As n grows, the same subproblems are recomputed exponentially many times.

Why It Matters

  • Without optimization: naive recursion solves the same subproblems repeatedly, leading to exponential time (e.g., O(2^n) for Fibonacci).

  • With memoization (top-down): cache results on first computation; subsequent calls return the cached value in O(1).

  • With tabulation (bottom-up): fill a table iteratively so each subproblem is solved exactly once in a defined order. Both techniques turn exponential time into polynomial time (O(n) for Fibonacci) at the cost of O(n) space.

Example: Fibonacci Recursion Tree

For fib(5) the naive recursive calls form this tree:

fib(5)├─ fib(4)│ ├─ fib(3)│ │ ├─ fib(2)│ │ │ ├─ fib(1) → 1│ │ │ └─ fib(0) → 0│ │ └─ fib(1) → 1│ └─ fib(2)│ ├─ fib(1) → 1│ └─ fib(0) → 0└─ fib(3) ├─ fib(2) │ ├─ fib(1) → 1 │ └─ fib(0) → 0 └─ fib(1) → 1

fib(2) is computed three times, fib(1) five times, fib(0) three times. With memoization each distinct fib(k) is evaluated once.

Relation to Optimal Substructure

Overlapping subproblems and optimal substructure are independent properties: - Optimal substructure: an optimal solution to the problem contains optimal solutions to its subproblems (enables DP formulation). - Overlapping subproblems: the same subproblems appear repeatedly (makes DP efficient). A problem needs both for classic DP to be the best approach. If subproblems don’t overlap, divide-and-conquer (e.g., mergesort) is sufficient.

Memoization vs Tabulation

Aspect Memoization (Top-Down) Tabulation (Bottom-Up)
Approach Recursive + cache Iterative table fill
Order On-demand Predefined (usually increasing index)
Space O(n) recursion stack + cache O(n) table (often optimizable to O(1))
Overhead Function call overhead None
When to use Easier to derive from recurrence Better performance, avoids recursion limit

Common Pitfalls

  • Confusing with optimal substructure: they are distinct; a problem can have one without the other.

  • Assuming all recursion has overlapping subproblems: mergesort and quicksort divide into disjoint subproblems, so DP adds no benefit.

  • Over-memoizing: caching subproblems that are never revisited wastes space.

  • Forgetting base cases: without correct base cases, memoized recursion still recurses infinitely.

  • Interview follow-up: “How would you reduce space from O(n) to O(1) for Fibonacci?” (Keep only the last two values). “When is top-down better than bottom-up?” (When the state space is sparse or recursion is more natural). “Can a problem have optimal substructure but no overlapping subproblems?” (Yes, e.g., binary search, mergesort).

3

How does memoization optimize Dynamic Programming?

Memoization is a caching technique that stores the result of an expensive computation and reuses it when the same inputs occur again. In Dynamic Programming, it prevents recursive subproblems from being solved repeatedly, often reducing exponential time to linear time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Memoization Works

A memoized recursive function follows this pattern:

  1. Return the result immediately if it is already cached.

  2. Handle the base cases.

  3. Compute the result for the current input.

  4. Store the result in the cache before returning it.

The cache key must represent every input that affects the result. In Python, functools.cache provides this behavior automatically.

Memoization is especially effective when a problem has:

  • Overlapping subproblems: The same state is evaluated multiple times.

  • Optimal substructure: An optimal result can be constructed from optimal results of smaller subproblems.

Memoization does not make an invalid recurrence correct; the recurrence must still have the required optimal-substructure property.

DP State and Recurrence

For Fibonacci, define the state as:

  • dp[n]: the nth Fibonacci number.

The recurrence is:

  • dp[0] = 0

  • dp[1] = 1

  • dp[n] = dp[n - 1] + dp[n - 2] for n >= 2

A top-down implementation evaluates dp[n] first and recursively requests smaller states. A bottom-up implementation computes states in increasing order, beginning with dp[0] and dp[1].

Without caching, recursive Fibonacci has an exponential call tree because values such as dp[n - 2] are recomputed repeatedly.

Code Example

The first function is the top-down memoized implementation. The second is a space-optimized bottom-up implementation used for comparison.

from functools import cache


@cache
def fibonacci_memo(n: int) -> int:
    """Return the nth Fibonacci number using top-down memoization."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n

    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)


def fibonacci_bottom_up(n: int) -> int:
    """Return the nth Fibonacci number using space-optimized tabulation."""
    if n < 0:
        raise ValueError("n must be non-negative")

    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current

    return previous


print(fibonacci_memo(10))      # 55
print(fibonacci_bottom_up(10))  # 55

For n > 0, fibonacci_bottom_up keeps only the two most recent DP values. It therefore reduces auxiliary space from O(n) to O(1).

Performance Comparison

Approach Time Auxiliary space When to use
Naive recursion O(φ^n) O(n) call stack Only for demonstrating the problem
Top-down memoization O(n) O(n) cache plus O(n) stack When the recurrence is naturally recursive
Bottom-up DP table O(n) O(n) When states should be evaluated in order
Space-optimized bottom-up O(n) O(1) When only the final result is required

Here φ is the golden ratio, approximately 1.618.

For a fresh Fibonacci computation, the best, average, and worst cases have the same stated complexity because the number of states is fixed by n.

  • Top-down memoization: O(n) time because each of the n + 1 states is computed once, assuming average O(1) cache operations. Auxiliary space is O(n), including both cached values and the recursion stack.

  • Space-optimized bottom-up: O(n) time because it performs n iterations, and O(1) auxiliary space because it stores only two values.

  • The scalar input itself is O(1) and is not included in auxiliary-space calculations.

Example DP Table

For n = 5:

i 0 1 2 3 4 5
dp[i] 0 1 1 2 3 5

The values are computed from left to right in bottom-up order. Top-down order is reversed: dp[5] is requested first, followed by its smaller dependencies.

Common Pitfalls

  • Wrong base cases: The recurrence must terminate, and base-case results must match the problem definition.

  • Incorrect cache keys: The key must include all inputs that can change the computed result.

  • Recursion-depth limits: Python’s default recursion limit is about 1,000. Large recursive DP inputs may fail, so iterative bottom-up DP is safer.

  • Unnecessary caching: Do not cache values outside the DP state space, and avoid keeping a large global cache when memory is constrained.

  • Ignoring space optimization: If only the final result is needed, retaining the complete DP table may be unnecessary.

  • Common follow-up questions: Interviewers often ask why the recurrence is correct, which states overlap, how the cache improves complexity, and how the space can be reduced.

4

Top-down vs bottom-up Dynamic Programming

Top-down and bottom-up are two ways to implement Dynamic Programming: top-down starts from the requested result and recursively computes smaller subproblems, while bottom-up starts from base cases and builds toward the final result. Both store or reuse previously computed states, but they differ in execution order, implementation style, and space usage.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Ideas

  • Top-down approach: Defines the recursive solution and memoizes results as they are needed.

  • Often called memoization.

  • Computes only states reachable from the initial request.

  • Uses a cache, dictionary, or table to avoid repeated work.

  • Bottom-up approach: Defines an iterative solution and computes states in a deliberate order, usually from smaller subproblems to larger ones.

  • Often called tabulation.

  • Can compute all states in the defined range, even if some are unnecessary.

  • Makes the computation order explicit and usually avoids recursion.

Both approaches rely on two required DP properties:

  • Overlapping subproblems: The same smaller problem is encountered multiple times, so its result should be reused.

  • Optimal substructure: The optimal solution to a larger problem can be constructed from optimal solutions to its smaller subproblems.

State, Recurrence, and Computation Order

For the Fibonacci example:

  • State: dp[i] means the value of the ith Fibonacci number.

  • Base cases: dp[0] = 0 and dp[1] = 1.

  • Recurrence: dp[i] = dp[i - 1] + dp[i - 2] for i >= 2.

  • Top-down computation: Start with dp[n], recursively request dp[n - 1] and dp[n - 2], and cache each result.

  • Bottom-up computation: Start with dp[0] and dp[1], then calculate dp[2] through dp[n] in increasing index order.

For a general problem, the same principles apply: define what each state represents, establish base cases, write a recurrence in terms of smaller states, and specify the order in which states are calculated.

Worked Example

For Fibonacci with n = 5:

i dp[i]
0 0
1 1
2 1
3 2
4 3
5 5

The bottom-up sequence is:

  1. Initialize dp[0] = 0 and dp[1] = 1.

  2. Calculate dp[2] = 1.

  3. Calculate dp[3] = 2.

  4. Calculate dp[4] = 3.

  5. Calculate dp[5] = 5.

The top-down version requests dp[5], then recursively computes dp[4] and dp[3]. When repeated states are encountered, the cached value is returned instead of recomputed.

Comparison

Approach Time Space Best, average, and worst case When to use
Top-down memoization O(n) O(n), including the cache and recursion stack Same in all cases When only a few states are needed or the recursive formulation is clearer
Bottom-up with full table O(n) O(n), including the DP table; input excluded Same in all cases When the state order is clear and all states are inexpensive to compute
Bottom-up with two variables O(n) O(1) auxiliary space; input excluded Same in all cases When the recurrence depends only on a fixed number of recent states

These bounds assume constant-time arithmetic. The reasons for the time complexity are that each Fibonacci state is computed once and the number of states is linear in n.

Common Pitfalls

  • Forgetting the base cases: A recurrence without valid base cases may recurse indefinitely or access invalid states.

  • Using the wrong computation order: Bottom-up code must calculate dependencies before the states that use them.

  • Ignoring recursion depth: The top-down Fibonacci example is safe for small inputs but can raise RecursionError for large n.

  • Confusing input space with auxiliary space: The stated DP space excludes the input itself.

  • Mutating the input accidentally: If an implementation modifies the input, state clearly whether that mutation is required.

  • Common follow-up questions: Interviewers may ask you to implement a different DP problem, identify the state and recurrence, optimize the DP table, or explain when memoization and tabulation are equivalent.

5

Why does state definition matter in Dynamic Programming?

A state definition specifies exactly what each DP entry represents. A precise definition determines the recurrence, base cases, computation order, and whether the algorithm correctly captures all information needed to solve the problem.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why State Definition Matters

Dynamic Programming works by solving overlapping subproblems and combining their results. The state definition identifies those subproblems.

A useful state definition answers three questions:

  • What information does the state contain?

  • Which smaller states are needed to calculate it?

  • What does one state represent in relation to the original problem?

An imprecise definition can produce several problems:

State definition Potential problem
“Best result for each index” Does not specify which houses, items, or characters may be selected
“Maximum value ending at position i” May omit whether the previous element can also be included
“Minimum cost to reach i” May not record the information required to make the next decision
“Ways to divide the input” May fail to distinguish valid and invalid partitions

If the state does not contain enough information, the recurrence cannot determine the correct answer. If it contains unnecessary information, the number of states may grow unnecessarily.

Required DP Components

For a well-defined Dynamic Programming solution:

  • State: dp[i] means the optimal answer for a precisely defined prefix or subproblem.

  • Recurrence: Expresses dp[i] using previously computed states.

  • Base cases: Define the answer when no decision remains, such as an empty prefix.

  • Computation order: Compute every dependency before the state that uses it.

A recurrence generally has the form:

dp[i] = optimal combination of dp[j] for one or more smaller states j

The state definition must make the meaning of both dp[i] and every referenced dp[j] unambiguous.

Top-down implementations express the recurrence through recursion and memoize results with functools.cache. Bottom-up implementations calculate the same states in a table, usually from smaller indices to larger ones. Both approaches require the same precise state definition.

Worked Example

Consider House Robber with houses [2, 7, 9, 3].

Define:

dp[i] is the maximum amount that can be robbed from the first i houses without choosing two adjacent houses.

The recurrence is:

dp[i] = max(dp[i - 1], dp[i - 2] + houses[i - 1])

The two choices are:

  • Skip house i - 1, leaving dp[i - 1].

  • Rob house i - 1, so house i - 2 cannot be robbed, giving dp[i - 2] + houses[i - 1].

Base cases are:

  • dp[0] = 0: No houses are available.

  • dp[1] = max(0, houses[0]): Choose whether to rob the first house.

States are computed in increasing order of i.

i Houses considered dp[i] Choice
0 [] 0 Base case
1 [2] 2 Rob house 0
2 [2, 7] 7 Rob house 1
3 [2, 7, 9] 11 Rob houses 0 and 2
4 [2, 7, 9, 3] 11 Rob houses 0 and 2

The answer is dp[4] = 11.

Overlapping Subproblems and Optimal Substructure

House Robber demonstrates the two properties required by Dynamic Programming:

  • Overlapping subproblems: Several choices repeatedly require states such as dp[i - 1]. Without memoization or tabulation, the same states are solved repeatedly.

  • Optimal substructure: An optimal solution can be decomposed into optimal solutions for smaller states. Whether the current house is robbed determines which smaller state contributes to the optimum.

A different state definition, such as “maximum amount robbed ending exactly at house i,” would require an additional state to handle whether the previous house was selected. The chosen prefix-based state avoids that extra dimension.

Complexity

For n houses:

Approach Time Auxiliary space Use
Brute-force subsets O(2^n) O(n) recursion stack Understand the problem or validate small cases
Memoized top-down O(n) O(n) cache plus O(n) recursion stack Closely follows the recurrence
Bottom-up table O(n) O(n) table Predictable computation and easy state tracing
Rolling variables O(n) O(1) Production solution when only the final answer is needed

Best, average, and worst-case time are all O(n) for the DP approaches because each of the n states is calculated once with constant work. The input array is not counted in auxiliary space; the DP table, cache, and recursion stack are.

In general, if there are S states and each state evaluates T transitions, time is O(S × T). Space is O(S), unless states can be discarded or compressed.

Common Pitfalls

  • Off-by-one errors: Clearly state whether dp[i] represents the first i elements or the element at index i.

  • Index inconsistency: Keep recurrence, base cases, and table columns aligned with the same convention.

  • Insufficient state: Include all historical decisions that can affect future choices.

  • Overlapping state dimensions: Avoid adding a dimension unless it distinguishes genuinely different situations.

  • Unclear base cases: Define behavior for empty inputs, single elements, and other boundary conditions.

  • Incorrect optimization: Before reducing space, verify that only the previous row or a fixed number of values are needed.

Interviewers commonly ask whether an alternative state could reduce the number of states, whether the recurrence captures every valid choice, and how the solution could be implemented with O(1) auxiliary space.

6

How to implement Fibonacci using Dynamic Programming?

Dynamic Programming computes Fibonacci by reusing previously calculated values instead of repeatedly solving the same subproblems. It reduces the naive recursive approach from exponentially many recursive calls to a linear number of computed states.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The Fibonacci recurrence says that each value is the sum of the preceding two values:

F(n) = F(n - 1) + F(n - 2)

The base cases are F(0) = 0 and F(1) = 1.

Dynamic Programming applies because: - Overlapping subproblems: Naive recursion repeatedly computes the same Fibonacci values. - Optimal substructure: F(n) is constructed from F(n - 1) and F(n - 2).

The state dp[i] represents the value of the i-th Fibonacci number.

  • Bottom-up order: Initialize dp[0] and dp[1], then compute dp[2] through dp[n] from smaller indices to larger ones.

  • Top-down order: Recursively request smaller indices on demand and memoize each result so it is computed only once.

The primary implementation below uses bottom-up iteration; the top-down variant demonstrates recursion with memoization.

For n = 5, the filled DP table is:

i dp[i] Calculation
0 0 Base case
1 1 Base case
2 1 dp[1] + dp[0]
3 2 dp[2] + dp[1]
4 3 dp[3] + dp[2]
5 5 dp[4] + dp[3]

Approaches Comparison

Approach Method Time Space When to use
Brute-force Naive recursion O(2^n) O(n) recursion stack Only as a baseline for small inputs
DP top-down Recursion plus cache O(n) O(n) cache and recursion stack When the recursive formulation maps directly to the problem
DP bottom-up Iterative DP table O(n) O(n) table When avoiding recursion and making computation order explicit

Code Example

import functools


def fibonacci_bottom_up(n: int) -> int:
    """Compute F(n) using an iterative dynamic-programming table."""
    if n < 0:
        raise ValueError("Input must be non-negative.")
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


def fibonacci_top_down(n: int) -> int:
    """Compute F(n) using recursion with memoization."""
    if n < 0:
        raise ValueError("Input must be non-negative.")

    @functools.cache
    def fib(index: int) -> int:
        if index <= 1:
            return index
        return fib(index - 1) + fib(index - 2)

    return fib(n)


print(fibonacci_bottom_up(5))  # 5
print(fibonacci_top_down(5))  # 5

Complexity Analysis

  • Bottom-up time: O(n), because each of the n states is computed once with constant-time arithmetic.

  • Bottom-up auxiliary space: O(n) for the DP table. Keeping only the previous two values reduces this to O(1) auxiliary space while retaining O(n) time.

  • Top-down time: O(n), because memoization ensures that each distinct state is evaluated once.

  • Top-down auxiliary space: O(n) for the cache plus O(n) for the recursion stack.

  • Input accounting: The scalar input n occupies O(1) space and is not included in the auxiliary-space totals.

  • These are conventional word-operation bounds. Python integers are arbitrary precision, so their bit-level operation and storage costs grow with the size of the Fibonacci values.

Common Pitfalls

  • Recursion limit: Top-down recursion can exceed Python’s default limit of approximately 1000 nested calls for sufficiently large n.

  • Off-by-one errors: The bottom-up loop must begin at index 2 and include index n.

  • Base cases: Handle n = 0 and n = 1 before indexing the table or recursing.

  • Negative input: Fibonacci is conventionally defined only for non-negative indices, so reject n < 0.

  • Follow-up questions: Interviewers commonly ask for an O(1)-space bottom-up solution or a logarithmic-time matrix-exponentiation solution.

7

How to solve the coin change problem with dynamic programming

The coin change problem asks for the minimum number of coins needed to reach a target amount from a given set of denominations. It is solved with dynamic programming by building a table of optimal solutions for every sub-amount from zero up to the target.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Concepts

  • Overlapping subproblems: A naive recursion recomputes the same sub-amounts many times.

  • Optimal substructure: The optimal solution for amount i uses the optimal solutions for i - coin for each coin.

  • State: dp[i] = minimum number of coins needed to make amount i.

  • Recurrence: dp[i] = min(dp[i - coin] + 1) for every coin where i - coin >= 0.

  • Base case: dp[0] = 0 (zero coins make amount zero).

  • Order: Compute from 0 to amount so every sub-problem is ready before it is needed.

Step-by-Step Example

For coins = [1, 2, 5] and amount = 11:

  1. dp[0] = 0.

  2. dp[1] = dp[0] + 1 = 1.

  3. dp[2] = min(dp[1] + 1, dp[0] + 1) = 1.

  4. dp[3] = min(dp[2] + 1, dp[1] + 1) = 2.

  5. dp[4] = min(dp[3] + 1, dp[2] + 1) = 2.

  6. dp[5] = min(dp[4] + 1, dp[3] + 1, dp[0] + 1) = 1.

  7. Continue to dp[11] = 3.

Filled DP Table

i 0 1 2 3 4 5 6 7 8 9 10 11
dp[i] 0 1 1 2 2 1 2 2 3 3 2 3

The answer is dp[11] = 3, using coins 5 + 5 + 1.

Code Example

The main implementation is bottom-up. A top-down version with functools.cache is also shown.

from functools import cache

def coin_change(coins: list[int], amount: int) -> int:
    """Minimum coins needed to make up `amount`, or -1 if impossible."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

def coin_change_top_down(coins: list[int], amount: int) -> int:
    """Top-down recursion with memoization. Needs sys.setrecursionlimit for large amounts."""
    @cache
    def dfs(remaining: int) -> int:
        if remaining == 0:
            return 0
        best = float('inf')
        for coin in coins:
            if remaining - coin >= 0:
                best = min(best, dfs(remaining - coin) + 1)
        return best
    result = dfs(amount)
    return result if result != float('inf') else -1

print(coin_change([1, 2, 5], 11))  # 3

Complexity

  • Time: O(amount × n) where n is the number of coins. Each of the amount states iterates over all n coins.

  • Space: O(amount) for the dp table. The input is not counted.

Brute-Force vs DP Comparison

Approach Time Complexity Space Complexity When to Use
Brute-force recursion O(n^amount) (exponential) O(amount) (recursion stack) Only for tiny amounts or illustration
Bottom-up DP O(amount × n) O(amount) All practical cases

Common Pitfalls

  • Forgetting to return -1 when the amount is unreachable.

  • Off-by-one errors in the loop range.

  • Not initializing dp with infinity, which can cause incorrect minimums.

  • The recursive version can exceed Python’s recursion limit for large amounts.

  • In languages with fixed-width integers, use a large sentinel (e.g., amount + 1) instead of infinity to avoid overflow.

  • Mutating the input coins list (e.g., sorting in place) can affect callers; work on a copy if needed.

  • The DP table itself acts as the visited set; no separate set is required.

  • Follow-up questions often ask: “How to reconstruct the actual coins used?” (store the last coin chosen) or “What if coins can be negative?” (amounts can then rise and fall, so the forward table no longer works; it becomes a shortest-path search over a bounded range of amounts).

8

How does dynamic programming solve the 0/1 Knapsack problem?

Dynamic programming solves 0/1 Knapsack by storing the best value for every relevant item-and-capacity state. Each item is either skipped or selected exactly once, so the algorithm avoids recomputing identical subproblems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

DP State, Recurrence, and Base Cases

Given a knapsack capacity C and n items with weights w[i] and values v[i], the goal is to maximize total value without exceeding capacity. The 0/1 restriction means each item can be selected at most once.

Let dp[i][c] be the maximum value obtainable using only the first i items with capacity c. The recurrence is:

[ dp[i][c] = max(dp[i-1][c],\ dp[i-1][c-w[i]] + v[i]) quad text{if } w[i] le c ]

Otherwise dp[i][c] = dp[i-1][c].

Base cases: - dp[0][c] = 0 (no items) - dp[i][0] = 0 (zero capacity)

Bottom-up computation processes items from 1 to n and capacities from 0 to C.

Filled DP Table Example
Items (weight, value): (2, 3), (3, 4), (4, 5), capacity 5.

Items considered 0 1 2 3 4 5
None 0 0 0 0 0 0
(2, 3) 0 0 3 3 3 3
(2, 3), (3, 4) 0 0 3 4 4 7
All three items 0 0 3 4 5 7

The optimal solution selects the first two items (total weight 5, value 7).

Overlapping Subproblems and Optimal Substructure

  • Overlapping subproblems: Many choices lead to the same state dp[i-1][c]. Memoization or a table computes each state once.

  • Optimal substructure: An optimal solution either excludes the current item or includes it; in the inclusion case the remaining items must be solved optimally for the remaining capacity.

Top-Down and Bottom-Up Approaches

Approach Time Space When to use
Brute-force enumeration O(2^n) O(n) recursion stack Small item counts only
Top-down memoization O(nC) O(nC) cache + O(n) stack When only some states are needed
Bottom-up tabulation O(nC) O(nC) table Straightforward, predictable implementation
Bottom-up with 1D array O(nC) O© Space-efficient implementation

The main implementation below uses bottom-up tabulation. A one-dimensional version reduces auxiliary space to O(C) by iterating capacities in descending order.

Code Example

from functools import cache


def solve_knapsack_top_down(
    capacity: int,
    items: list[tuple[int, int]],
) -> int:
    """Return the maximum value for the 0/1 Knapsack problem."""
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    if any(weight <= 0 for weight, _ in items):
        raise ValueError("item weights must be positive")

    @cache
    def best(index: int, remaining: int) -> int:
        if index == len(items) or remaining == 0:
            return 0

        weight, value = items[index]
        skip = best(index + 1, remaining)

        take = 0
        if weight <= remaining:
            take = value + best(index + 1, remaining - weight)

        return max(skip, take)

    return best(0, capacity)


def solve_knapsack(
    capacity: int,
    items: list[tuple[int, int]],
) -> int:
    """Return the maximum value using bottom-up dynamic programming."""
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    if any(weight <= 0 for weight, _ in items):
        raise ValueError("item weights must be positive")

    item_count = len(items)
    dp = [[0] * (capacity + 1) for _ in range(item_count + 1)]

    for item_index, (weight, value) in enumerate(items, start=1):
        for current_capacity in range(capacity + 1):
            dp[item_index][current_capacity] = dp[item_index - 1][current_capacity]

            if weight <= current_capacity:
                dp[item_index][current_capacity] = max(
                    dp[item_index][current_capacity],
                    dp[item_index - 1][current_capacity - weight] + value,
                )

    return dp[item_count][capacity]


items = [(2, 3), (3, 4), (4, 5)]
print(solve_knapsack(5, items))  # Expected output: 7
print(solve_knapsack_top_down(5, items))  # Expected output: 7

Complexity, Edge Cases, and Common Pitfalls

For n items and capacity C:

  • Time: O(nC) best, average, and worst case. Each table entry is computed once with constant work.

  • Auxiliary space: O(nC) for the bottom-up table (excluding input). Top-down uses O(nC) cache plus O(n) recursion stack (excluding input). The 1D optimization reduces space to O(C).

Handled or defined edge cases: - Empty item list: returns 0 - Zero capacity: returns 0 - One item: returns its value if weight fits, otherwise 0 - Duplicate items: treated as separate items, each usable once - Negative values: allowed; they are naturally not selected unless they enable a better valid combination - Negative weights or capacities: rejected (standard assumptions require positive weights, non‑negative capacity)

Common pitfalls: - Off-by-one errors: Ensure dp[i][c] definition matches recurrence and table dimensions. - Using items repeatedly: In 1D optimization, iterate capacities backward. - Ignoring the 0/1 constraint: Use the previous row, not the current row, in the 2D recurrence. - Mutating the input: The examples preserve items. - Integer overflow in other languages: Use sufficiently wide integer types. - Interview follow-ups: Be ready to explain why the recurrence is optimal, compare with greedy approaches, and describe the O(C) space‑optimized variant.

9

How do you implement the longest common subsequence algorithm?

The longest common subsequence (LCS) is the longest sequence that appears in both input sequences in the same relative order. Dynamic programming compares progressively longer prefixes and can either calculate the LCS length or reconstruct one optimal subsequence.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let dp[i][j] represent the length of the LCS between:

  • The first i elements of the left sequence

  • The first j elements of the right sequence

The recurrence is:

  • If left[i - 1] == right[j - 1], then
    dp[i][j] = 1 + dp[i - 1][j - 1]

  • Otherwise,
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

The base cases are:

  • dp[0][j] = 0 for every j

  • dp[i][0] = 0 for every i

Compute cells from smaller prefixes to larger prefixes so every required subproblem is already available.

DP is appropriate because the problem has:

  • Overlapping subproblems: The same prefix comparisons are reused repeatedly.

  • Optimal substructure: The optimal LCS of larger prefixes depends on optimal solutions for smaller prefix problems.

Top-Down and Bottom-Up

The top-down version uses recursion with functools.cache. Its recursion depth can exceed Python’s default limit for long sequences.

The bottom-up version fills a table iteratively. The main implementation below uses bottom-up DP because it avoids recursion-depth issues and can reconstruct an LCS by walking backward through the table.

For sequence lengths m and n:

  • Bottom-up time: O(mn) in the best, average, and worst cases because every table cell is computed.

  • Top-down time: O(mn) in the average and worst cases. The best case is O(m + n) when matches keep traversal on the diagonal, such as for identical sequences.

  • Bottom-up auxiliary space: O(mn) in all cases for the table.

  • Top-down auxiliary space: O(mn) in the average and worst cases, including memoized states and the recursion stack; it is O(m + n) in the best diagonal case.

  • The input sequences are not counted.

If only the LCS length is needed, bottom-up DP can keep one previous row, reducing auxiliary space to O(min(m, n)). Reconstructing a subsequence requires additional information, such as the full table or backpointers.

Filled DP Table

For left = "ABCBD" and right = "BDC":

Prefix of left Prefix of right Empty B BD BDC
Empty 0 0 0 0
A 0 0 0 0
AB 0 1 1 1
ABC 0 1 1 2
ABCB 0 1 1 2
ABCBD 0 1 2 2

The LCS length is 2. One valid LCS is "BD".

Code Example

from collections.abc import Hashable, Sequence
from functools import cache


def lcs_length_top_down(
    left: Sequence[Hashable],
    right: Sequence[Hashable],
) -> int:
    """Return the LCS length using top-down dynamic programming."""
    left_tuple = tuple(left)
    right_tuple = tuple(right)

    @cache
    def dp(left_index: int, right_index: int) -> int:
        if left_index == len(left_tuple) or right_index == len(right_tuple):
            return 0

        if left_tuple[left_index] == right_tuple[right_index]:
            return 1 + dp(left_index + 1, right_index + 1)

        return max(
            dp(left_index + 1, right_index),
            dp(left_index, right_index + 1),
        )

    return dp(0, 0)


def longest_common_subsequence(
    left: Sequence[Hashable],
    right: Sequence[Hashable],
) -> tuple[Hashable, ...]:
    """Return one longest common subsequence using bottom-up DP."""
    left_length = len(left)
    right_length = len(right)

    dp = [
        [0] * (right_length + 1)
        for _ in range(left_length + 1)
    ]

    for left_index in range(1, left_length + 1):
        for right_index in range(1, right_length + 1):
            if left[left_index - 1] == right[right_index - 1]:
                dp[left_index][right_index] = (
                    1 + dp[left_index - 1][right_index - 1]
                )
            else:
                dp[left_index][right_index] = max(
                    dp[left_index - 1][right_index],
                    dp[left_index][right_index - 1],
                )

    result: list[Hashable] = []
    left_index = left_length
    right_index = right_length

    while left_index > 0 and right_index > 0:
        if left[left_index - 1] == right[right_index - 1]:
            result.append(left[left_index - 1])
            left_index -= 1
            right_index -= 1
        elif dp[left_index][right_index - 1] >= dp[left_index - 1][right_index]:
            right_index -= 1
        else:
            left_index -= 1

    result.reverse()
    return tuple(result)


print(lcs_length_top_down("ABCBD", "BDC"))  # 2
print(longest_common_subsequence("ABCBD", "BDC"))  # ('B', 'D')

Common Pitfalls

  • Empty input: If either sequence is empty, the result is an empty subsequence with length 0.

  • One element: A one-element sequence contributes length 1 only if its element occurs in the other sequence.

  • Duplicates: Equal elements do not need to be unique, but their relative order must be preserved.

  • Negative or sorted values: These are valid elements or inputs; the algorithm requires no special handling and must not sort either input.

  • Off-by-one errors: dp[i][j] uses prefix lengths, while sequence access uses i - 1 and j - 1.

  • Recursion depth: The top-down implementation may require a raised recursion limit for long sequences; bottom-up DP avoids this issue.

  • Input mutation and overflow: Neither implementation mutates the inputs. In fixed-width languages, ensure dimensions such as max(m, n) + 1 do not overflow.

  • LCS versus longest common substring: LCS elements need not be contiguous; a substring must be contiguous.

  • Tie handling: Either predecessor may be chosen when their values tie, producing a different but equally long LCS.

  • Common follow-up: Interviewers may ask for the LCS length versus reconstruction, all possible LCS solutions, the longest common substring, or an extension to multiple sequences.

10

How to solve matrix chain multiplication using dynamic programming

The Matrix Chain Multiplication problem finds the optimal parenthesization of a sequence of matrices to minimize the total number of scalar multiplications. It is a classic dynamic programming problem that relies on the properties of optimal substructure and overlapping subproblems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The problem exhibits optimal substructure because the optimal solution for a chain of matrices i to j contains optimal solutions for sub-chains. It exhibits overlapping subproblems because the same sub-chains are solved repeatedly in a naive recursive approach.

  • State: dp[i][j] represents the minimum number of scalar multiplications needed to compute the product of matrices from index i to j.

  • Recurrence: To compute dp[i][j], split the chain at every possible position k between i and j-1. The cost is the sum of the cost of the left sub-chain, the cost of the right sub-chain, and the cost of multiplying the two resulting matrices.

  • Base Case: dp[i][i] = 0 because a single matrix requires no multiplication.

  • Order of Computation: Fill the table by chain length, starting from length 2 up to n. This ensures that when dp[i][j] is computed, all smaller sub-chain costs are already known.

A top-down approach using recursion with functools.cache is also valid, but the bottom-up table approach is preferred here to avoid recursion depth limits.

Brute Force vs Dynamic Programming

A brute-force approach explores all possible parenthesizations, which corresponds to the Catalan numbers.

Approach Time Complexity Space Complexity When to Use
Brute Force O(4^n / n^(3/2)) O(n) Small n, conceptual understanding
Dynamic Programming O(n^3) O(n^2) All practical cases

Complexity Analysis

  • Time Complexity: O(n^3). There are three nested loops: one for the chain length, one for the starting matrix, and one for the split point.

  • Space Complexity: O(n^2). This is the size of the dp table. Space optimization to O(n) is not straightforward here because the dependencies span the entire table, and the table is needed to reconstruct the optimal parenthesization.

Step-by-Step Example

Consider dimensions p = [10, 20, 30, 40]. There are 3 matrices: A0 (10x20), A1 (20x30), A2 (30x40).

  1. Length 2:

  2. dp[0][1] (A0 x A1): 10 * 20 * 30 = 6000

  3. dp[1][2] (A1 x A2): 20 * 30 * 40 = 24000

  4. Length 3:

  5. dp[0][2] (A0 x A1 x A2):

    • Split at k=0: dp[0][0] + dp[1][2] + 10 * 20 * 40 = 0 + 24000 + 8000 = 32000

    • Split at k=1: dp[0][1] + dp[2][2] + 10 * 30 * 40 = 6000 + 0 + 12000 = 18000

    • Minimum is 18000.

Filled DP Table (0-based indices):

i j 0 1 2
0 0 6000 18000
1 - 0 24000
2 - - 0

Code Example

Bottom-up (iterative) – main implementation used for large n to avoid recursion limits:

def matrix_chain_order(p: list[int]) -> int:
    """
    Calculates the minimum number of scalar multiplications needed
    to compute the matrix chain product.

    Args:
        p: A list of dimensions where matrix i has dimensions
           p[i] x p[i+1]. Length must be at least 2.

    Returns:
        The minimum cost to multiply the chain of matrices.
    """
    n = len(p) - 1
    if n <= 1:
        return 0

    # dp[i][j] stores the minimum cost for matrices i through j
    dp = [[0] * n for _ in range(n)]

    # Fill the table for chain lengths 2 to n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            # Find the best split point k
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

# matrix_chain_order([10, 20, 30, 40]) returns 18000

Top-down (memoized recursive) – alternative using functools.cache:

from functools import cache

def matrix_chain_order_top_down(p: list[int]) -> int:
    """
    Top-down (memoized recursive) solution for matrix chain multiplication.
    Returns the minimum cost.
    """
    n = len(p) - 1
    if n <= 1:
        return 0

    @cache
    def dp(i: int, j: int) -> int:
        if i == j:
            return 0
        min_cost = float('inf')
        for k in range(i, j):
            cost = dp(i, k) + dp(k + 1, j) + p[i] * p[k + 1] * p[j + 1]
            if cost < min_cost:
                min_cost = cost
        return min_cost

    return dp(0, n - 1)

# matrix_chain_order_top_down([10, 20, 30, 40]) returns 18000

Common Pitfalls

  • Off-by-one errors: The dimensions array p has length n+1, and matrix i uses p[i] and p[i+1]. Confusing these indices is a common source of bugs.

  • Initialization: Forgetting to initialize dp[i][j] to infinity before taking the minimum will result in incorrect results.

  • Recursion Depth: A naive recursive solution without memoization will time out, and even with memoization, Python’s default recursion limit may be exceeded for large n. The iterative bottom-up approach avoids this.

  • Space Constraints: If you only need the cost and not the parenthesization, the space complexity remains O(n^2) in the standard implementation.

  • Follow-up: Interviewers often ask how to reconstruct the actual parenthesization, which requires storing the split points in a separate table.

11

How do memoization and tabulation compare in Dynamic Programming?

Memoization is the top-down form of Dynamic Programming, while tabulation is the bottom-up form. Both avoid repeated work by storing solved subproblems, but they differ in computation order, recursion usage, memory usage, and which states they evaluate.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Both approaches rely on two properties:

  • Overlapping subproblems: multiple recursive paths encounter the same state and would otherwise repeat identical calculations.

  • Optimal substructure: an optimal result can be constructed from optimal results for smaller subproblems.

Memoization starts from the requested state and recursively computes only the dependencies it encounters. Tabulation starts from known base cases and systematically fills a table in dependency order.

State, Recurrence, and Order

Using the climbing-stairs problem as an example:

  • State: ways[i] is the number of distinct ways to climb i stairs when each move covers either one or two stairs.

  • Base cases: ways[0] = 1 and ways[1] = 1.

  • Recurrence: ways[i] = ways[i - 1] + ways[i - 2] for i >= 2.

  • Memoization order: recursively evaluates dependencies, effectively computing smaller states while unwinding the call stack.

  • Tabulation order: explicitly computes states from 0 through the target.

For steps = 4, the filled table is:

State i 0 1 2 3 4
ways[i] 1 1 2 3 5

Memoization Versus Tabulation

Aspect Memoization Tabulation
Direction Top-down Bottom-up
Starting point Target state Base cases
State evaluation Computes reachable states Usually computes all states in the valid range
Storage Memoization cache, often a dictionary Preallocated table or array
Recursion Requires recursion and a call stack Can be entirely iterative
Memory Cache plus recursion stack Table only; iterative stack is constant space
Dependency order Handled automatically through recursion Must be identified explicitly
Performance profile Can avoid irrelevant states May perform unnecessary work but has predictable execution
Stack risk Can exceed Python’s recursion limit No recursive stack risk
Debugging Follows the recursive call tree Makes all intermediate states visible

Choose memoization when only a small subset of states is reachable or when the recurrence is naturally recursive. Choose tabulation when the state space is regular, the dependency order is clear, or recursion depth could become a problem.

Complexity

For the climbing-stairs recurrence:

  • Memoization

  • Best, average, and worst-case time: O(n). Each state is computed once, and each state examines two dependencies.

  • Auxiliary space: O(n). The cache uses O(n) space and the recursion stack also reaches O(n).

  • Tabulation

  • Best, average, and worst-case time: O(n). The loop computes each state once.

  • Auxiliary space: O(n) for the table. The iterative call stack uses O(1).

  • With only the previous two values retained, space can be optimized to O(1), although all intermediate states are then unavailable for reconstruction.

These complexities count auxiliary space, including the recursion stack, but exclude the original input. If the input itself contains n elements, it separately occupies O(n) space.

For a general DAG of states, both methods usually take O(S + E) time, where S is the number of states and E is the number of dependency transitions. Memoization evaluates only reachable states, whereas tabulation may evaluate additional states.

Common Pitfalls

  • Off-by-one errors: Define whether state 0 represents an empty solution, one way, or an invalid configuration.

  • Incorrect initialization: Tabulation must initialize every required base case before filling dependent states.

  • Unbounded recursion: Top-down solutions can exceed Python’s default recursion limit of roughly 1,000 calls.

  • Unnecessary work: Bottom-up code may compute states that the target does not actually require.

  • Incorrect fill order: A tabulated state must be computed only after every state it depends on.

  • Lost reconstruction data: If the answer requires an optimal sequence, store predecessor or choice information alongside each value.

12

What determines the time complexity of a Dynamic Programming algorithm?

The time complexity of a Dynamic Programming algorithm is determined primarily by the number of distinct states computed and the work performed for each state. If there are S states and C constant-time candidate transitions per state, the running time is O(S × C); when each state has constant work, this becomes O(S).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Method

  1. Define the state: Specify what dp[i] or dp[i][j] represents.

  2. Write the recurrence: Express each state in terms of smaller, already-solved states.

  3. Identify base cases: Define the states that require no further computation.

  4. Determine evaluation order: Compute dependencies before the states that depend on them.

  5. Count states and transitions:

  6. A one-dimensional problem with n positions generally has O(n) states.

  7. A two-dimensional problem with dimensions n and m generally has O(nm) states.

  8. If each state examines k choices, the complexity is O(nk) for one dimension or O(nmk) for two dimensions.

More precisely, the time is O(S + E), where S is the number of computed states and E is the number of dependency transitions evaluated, assuming constant-time state access and constant-time transition work. If transition work is not constant, its actual cost must also be included.

For a fixed state graph, best, average, and worst-case time are all O(S + E). If only reachable states are computed, their number may vary by input: the best case uses the smallest reachable state set, the average case depends on the input distribution, and the worst case includes the largest reachable state set.

Required DP Properties

  • Overlapping subproblems: Multiple computations depend on the same smaller states. Memoization or bottom-up computation avoids repeating that work.

  • Optimal substructure: An optimal solution can be constructed from optimal solutions to the subproblems represented by the recurrence.

If subproblems do not overlap, memoization may not reduce the work. If optimal substructure is absent, Dynamic Programming may not apply directly.

Example State Table

For Fibonacci numbers:

  • State: dp[i] is the ith Fibonacci number.

  • Recurrence: dp[i] = dp[i - 1] + dp[i - 2].

  • Base cases: dp[0] = 0 and dp[1] = 1.

  • Order: Compute dp[2] through dp[n] from left to right.

i 0 1 2 3 4 5
dp[i] 0 1 1 2 3 5

Under the usual unit-cost arithmetic model, there are O(n) states and one constant-time addition per state, so the running time is O(n).

Complexity Comparison

Approach Time Auxiliary space When to use
Naive recursion O(2^n) O(n) recursion stack As a baseline for very small inputs
Top-down with memoization O(n) O(n) cache plus O(n) recursion stack When only some states are reachable
Bottom-up table O(n) O(n) table When most states are needed
Bottom-up with two variables O(n) O(1) When only the latest states are required

These space bounds exclude the input itself but include the recursion stack. If the input is an array of length n, counting it adds O(n) total space. In bit-level accounting, Python’s arbitrary-precision integers change the Fibonacci bounds: the bottom-up approach can require O(n²) bit operations and O(n) bits of working numeric storage, while the memoized table can require O(n²) bits.

Common Pitfalls

  • Counting states while ignoring the work performed inside each state.

  • Confusing the number of possible states with the number actually reachable.

  • Assuming arithmetic is constant-time when values exceed machine-word or fixed-width limits.

  • Ignoring integer overflow in fixed-width languages; use a sufficiently wide type or modular arithmetic when appropriate.

  • Mutating the input when a read-only DP table would preserve it.

  • Forgetting the visited set when DP is combined with graph traversal, causing cycles to be revisited.

  • Making off-by-one errors in base cases or loop bounds, especially for empty and single-element inputs.

  • Assuming every DP solution needs a full table when previous-row or constant-space optimization is possible.

Interviewers commonly ask how the state count was derived, why the recurrence is optimal, how base cases handle edge cases, and how auxiliary space can be reduced.

13

How can Dynamic Programming space complexity be optimized?

Space optimization reduces the memory required by Dynamic Programming while preserving the same optimal result. Common approaches include rolling arrays, updating a DP table in place, computing only reachable states, and compressing multidimensional states.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Techniques

  • Rolling arrays: If computing row i depends only on row i-1, retain two rows instead of the entire table. This typically changes O(nW) auxiliary space to O(W).

  • In-place updates: A single array can represent the required previous states when items are processed in a safe order. For 0/1 knapsack, capacities are processed backward.

  • Top-down memoization: Cache only states reached from the initial state. This can save memory when most states are irrelevant, although the recursion stack still consumes O(n) space.

  • State compression: Encode a set of dimensions into a smaller representation, such as a bitmask, when the number of possible states is small.

  • Remove redundant dimensions: Sometimes two-dimensional or higher-dimensional states depend on a simpler relationship that allows a one-dimensional formulation.

  • Exploit special structure: Prefix sums, monotonicity, or divide-and-conquer transitions can reduce retained state. A greedy solution should replace DP only when equivalence can be proven.

DP Formulation

Before optimizing memory, define the problem precisely:

  • State: dp[i][w] represents the maximum value obtainable using the first i items with capacity w.

  • Recurrence: For item i, either skip it or take it when it fits: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight] + value).

  • Base cases: dp[0][w] = 0, because selecting no items produces zero value.

  • Computation order: Compute rows in increasing i. The one-dimensional implementation processes capacities in decreasing order so each item is used at most once.

Dynamic Programming is appropriate when there are overlapping subproblems, where multiple paths reach the same state, and optimal substructure, where an optimal result can be constructed from optimal results of smaller states.

Worked Example

For weights [2, 3, 4], values [3, 4, 5], and capacity 5, the filled DP table is:

Items considered 0 1 2 3 4 5
None 0 0 0 0 0 0
Weight 2, value 3 0 0 3 3 3 3
Weights 2, 3 0 0 3 4 4 7
Weights 2, 3, 4 0 0 3 4 5 7

The optimal solution selects weights 2 and 3, producing value 7.

Complexity Comparison

Let n be the number of items and W the capacity.

Approach Time Auxiliary space Including input When to use
Top-down with functools.cache O(nW) O(nW) for cache plus O(n) recursion stack O(nW + n + W) Many states are unreachable
Bottom-up table O(nW) O(nW) O(nW + n + W) Most states are relevant
One-dimensional bottom-up O(nW) O(W) O(n + W) Transitions depend on one previous row

The main implementation below uses the one-dimensional approach. Best, average, and worst-case complexities are identical because DP has deterministic state-processing costs.

Code Example

from functools import cache
from typing import Sequence


def knapsack_top_down(
    weights: Sequence[int], values: Sequence[int], capacity: int
) -> int:
    """Return the maximum 0/1 knapsack value using memoized recursion."""
    if len(weights) != len(values):
        raise ValueError("weights and values must have equal lengths")
    if any(weight < 0 for weight in weights):
        raise ValueError("weights cannot be negative")
    if capacity <= 0 or not weights:
        return 0

    @cache
    def best(index: int, remaining: int) -> int:
        if index == len(weights) or remaining == 0:
            return 0

        skip = best(index + 1, remaining)
        take = 0
        if weights[index] <= remaining:
            take = values[index] + best(
                index + 1, remaining - weights[index]
            )
        return max(skip, take)

    return best(0, capacity)


def knapsack_bottom_up(
    weights: Sequence[int], values: Sequence[int], capacity: int
) -> int:
    """Return the maximum 0/1 knapsack value using a two-dimensional table."""
    if len(weights) != len(values):
        raise ValueError("weights and values must have equal lengths")
    if any(weight < 0 for weight in weights):
        raise ValueError("weights cannot be negative")
    if capacity <= 0 or not weights:
        return 0

    dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]

    for index, (weight, value) in enumerate(zip(weights, values), start=1):
        for limit in range(capacity + 1):
            dp[index][limit] = dp[index - 1][limit]
            if weight <= limit:
                dp[index][limit] = max(
                    dp[index][limit],
                    dp[index - 1][limit - weight] + value,
                )

    return dp[len(weights)][capacity]


def knapsack_space_optimized(
    weights: Sequence[int], values: Sequence[int], capacity: int
) -> int:
    """Return the maximum 0/1 knapsack value using one DP array."""
    if len(weights) != len(values):
        raise ValueError("weights and values must have equal lengths")
    if any(weight < 0 for weight in weights):
        raise ValueError("weights cannot be negative")
    if capacity <= 0 or not weights:
        return 0

    dp = [0] * (capacity + 1)

    for weight, value in zip(weights, values):
        # Descending order prevents the current item from being reused.
        for limit in range(capacity, weight - 1, -1):
            dp[limit] = max(dp[limit], dp[limit - weight] + value)

    return dp[capacity]


if __name__ == "__main__":
    result = knapsack_space_optimized([2, 3, 4], [3, 4, 5], 5)
    print(result)  # Expected output: 7

Common Pitfalls

  • Updating 0/1 knapsack capacities in ascending order can accidentally allow unlimited use of an item.

  • In-place updates are safe only when every transition reads states that have not yet been overwritten.

  • Top-down recursion can exceed Python’s default recursion limit for large inputs; use the iterative implementation or an explicit stack.

  • Exclude input storage when reporting auxiliary space, but state whether the reported total includes the input.

  • Verify base cases for empty input, zero capacity, one item, duplicates, and negative values. Negative weights are invalid for this formulation.

14

How to define and derive state transitions in dynamic programming

A state transition is a recurrence rule that computes a dynamic-programming state from already solved dependency states. Deriving one requires a precise state definition, exhaustive base cases, and a recurrence that captures the problem’s optimal substructure.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concepts

  • State: Precisely describes a subproblem, such as dp[i] representing the number of ways to reach step i.

  • Overlapping subproblems: Different states repeatedly require the same smaller states, so results should be stored and reused.

  • Optimal substructure: An optimal solution can be constructed from optimal solutions to its dependency states.

  • Transition: Computes one state from dependency states, usually by considering the possible final decisions or choices.

Deriving a Transition

  1. Define the state: Specify exactly what dp[i] or dp[i][j] represents.

  2. Identify base cases: Record the answers for states that can be computed directly.

  3. Enumerate final choices: Partition all valid possibilities into exhaustive, disjoint cases.

  4. Write the recurrence: Express each case using smaller dependency states, then combine the results.

  5. Choose the computation order: Compute each dependency before the state that uses it.

  6. Check the result: Test small inputs manually and confirm that the recurrence neither omits nor double-counts solutions.

For climbing stairs, let dp[i] be the number of ways to reach step i using moves of one or two steps. The base cases are dp[0] = 1 and dp[1] = 1. For i >= 2, the final move comes from either i - 1 or i - 2, so:

dp[i] = dp[i - 1] + dp[i - 2]

The two cases are exhaustive and disjoint. Bottom-up computation fills states in increasing order, from i = 2 through n.

Approach Comparison

Approach Time Space When to use
Brute-force recursion O(2^n) O(n) recursion stack Only for very small inputs or proof of recurrence
Top-down with memoization O(n) O(n) cache plus O(n) stack When the recurrence is naturally recursive
Bottom-up table O(n) O(n) table Main implementation; avoids recursion limits
Bottom-up with two variables O(n) O(1) auxiliary space When only the final result is needed

The main implementation below uses the bottom-up table.

Code Example

i 0 1 2 3 4 5
dp[i] 1 1 2 3 5 8
from functools import cache


def climb_stairs_top_down(n: int) -> int:
    """Return the ways to reach step n using one- or two-step moves."""
    if n < 0:
        raise ValueError("n must be non-negative")

    @cache
    def dp(step: int) -> int:
        if step <= 1:
            return 1
        return dp(step - 1) + dp(step - 2)

    return dp(n)


def climb_stairs(n: int) -> int:
    """Return the ways to reach step n using one- or two-step moves."""
    if n < 0:
        raise ValueError("n must be non-negative")

    ways = [0] * (n + 1)
    ways[0] = 1
    if n >= 1:
        ways[1] = 1

    for step in range(2, n + 1):
        ways[step] = ways[step - 1] + ways[step - 2]

    return ways[n]


print(climb_stairs(5))  # 8

Complexity and Edge Cases

  • Top-down time: O(n), because each of the O(n) states is computed once.

  • Top-down space: O(n), including the memoization cache and O(n) recursion stack.

  • Bottom-up time: O(n), because the table contains n + 1 entries.

  • Bottom-up space: O(n) for the table, reducible to O(1) by retaining only the previous two values.

  • The input itself is not counted in auxiliary space.

  • n = 0 returns 1, representing the empty sequence of moves; n = 1 returns 1; negative n raises ValueError.

  • Top-down recursion can exceed Python’s default recursion limit of roughly 1000, so the iterative implementation is safer for large inputs.

Common Pitfalls

  • Off-by-one errors in base cases, table sizes, or loop boundaries.

  • Ambiguous state definitions or recurrences with missing or overlapping cases.

  • Forgetting to initialize every dependency before using it.

  • Integer overflow in fixed-width languages; use an sufficiently wide integer type.

  • Mutating inputs unnecessarily or, in graph DP, forgetting visited-state tracking around cycles.

  • Common follow-up questions ask for a correctness proof, reduced space complexity, or how the recurrence changes when constraints change.

15

How to find the longest palindromic substring in a string

The longest palindromic substring can be found using dynamic programming by determining which substrings are palindromes and retaining the longest one. The implementation below returns the earliest occurrence when several longest palindromes exist.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • State: dp[i][j] is True when the substring s[i..j] is a palindrome.

  • Recurrence: dp[i][j] = (s[i] == s[j]) and (j - i < 2 or dp[i+1][j-1]).

  • Base cases: Every single character is a palindrome. Two characters form a palindrome exactly when they are equal.

  • Order: Compute intervals in increasing length so that the required shorter interval is already known.

  • Overlapping subproblems: A naïve scan of every candidate can repeatedly inspect interior ranges shared by overlapping candidates. DP records palindrome information by interval and avoids those repeated scans.

  • Optimal substructure: The decision for s[i..j] depends only on endpoint equality and the correct smaller result for s[i+1..j-1].

  • The main implementation uses a bottom-up table compressed to a constant number of length rows. A top-down recursive version is also shown.

DP Table Example

For s = "babad", the upper-triangular table contains:

i j 0 1 2 3 4
0 T F T F F
1 — T F T F
2 — — T F F
3 — — — T F
4 — — — — T

The longest palindromes are "bab" at dp[0][2] and "aba" at dp[1][3].

Approach Comparison

Approach Time Auxiliary space When to use
Brute-force substring checking O(n³) best, average, worst O(1) Very short strings
Full 2D DP table O(n²) best, average, worst O(n²) When the complete table is useful
Rolling-row DP O(n²) best, average, worst O(n) General implementation with lower memory use
Expand around center O(n) best, O(n) expected average for random fixed-alphabet strings, O(n²) worst O(1) When minimum auxiliary space matters

Code Example

from functools import cache


def longest_palindromic_substring_top_down(s: str) -> str:
    """Return the earliest longest palindromic substring using memoization."""
    if not s:
        return ""

    n = len(s)

    @cache
    def is_palindrome(left: int, right: int) -> bool:
        if left >= right:
            return True
        return s[left] == s[right] and is_palindrome(left + 1, right - 1)

    best_start = 0
    best_length = 1

    for left in range(n):
        for right in range(left, n):
            length = right - left + 1
            if length > best_length and is_palindrome(left, right):
                best_start = left
                best_length = length

    return s[best_start : best_start + best_length]


def longest_palindromic_substring(s: str) -> str:
    """Return the earliest longest palindromic substring using rolling DP rows."""
    if not s:
        return ""

    n = len(s)
    best_start = 0
    best_length = 1

    # Intervals of length 1 are palindromes.
    previous: list[bool] = [True] * n
    previous_previous: list[bool] = []

    for length in range(2, n + 1):
        current = [False] * n

        for left in range(n - length + 1):
            right = left + length - 1
            if s[left] == s[right] and (
                length == 2 or previous_previous[left + 1]
            ):
                current[left] = True
                if length > best_length:
                    best_start = left
                    best_length = length

        # Shift rows so the next iteration can access lengths L-2 and L-1.
        previous_previous, previous = previous, current

    return s[best_start : best_start + best_length]


print(longest_palindromic_substring_top_down("babad"))  # bab
print(longest_palindromic_substring("babad"))  # bab

Complexity

  • Bottom-up rolling DP: O(n²) time in the best, average, and worst cases. It uses O(n) auxiliary space, excluding the input string.

  • Full 2D DP: O(n²) time and O(n²) auxiliary space, excluding the input.

  • Top-down DP: O(n²) time in all cases. The cache uses O(n²) space and the recursion stack uses O(n) space, so total auxiliary space is O(n²), excluding the input.

  • Long strings can exceed Python’s default recursion limit of roughly 1,000 in the top-down version; use the iterative implementation or carefully raise sys.setrecursionlimit().

Common Pitfalls

  • Off-by-one errors in interval boundaries and recurrence indexes.

  • Accidentally replacing an earlier answer with a later palindrome of equal length.

  • Empty and one-character inputs must be handled explicitly; repeated characters may create palindromes spanning most of the string.

  • The top-down solution must use memoization to avoid repeated recursive work.

  • Negative-number, sorted-input, disconnected-graph, and cycle cases do not apply to this string problem.

  • Interviewers commonly follow up by asking for expand-around-center or the O(n) Manacher algorithm.

16

How do you solve edit distance using dynamic programming?

Edit distance is the minimum number of single-character insertions, deletions, or substitutions needed to transform one string into another. Dynamic programming efficiently reuses results for overlapping string-prefix problems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Dynamic Programming Approach

Let m be the source string’s length and n the target string’s length.

Define dp[i][j] as the minimum edit cost of converting the first i characters of source into the first j characters of target.

The approach relies on two properties:

  • Overlapping subproblems: Many prefix comparisons require the same smaller comparison, such as dp[i - 1][j - 1].

  • Optimal substructure: An optimal transformation can be constructed from optimal transformations of smaller prefixes.

State, Recurrence, and Computation

The base cases are:

  • dp[0][j] = j: insert all j target characters into an empty source.

  • dp[i][0] = i: delete all i source characters to obtain an empty target.

For nonempty prefixes:

  • If source[i - 1] == target[j - 1], the characters match:

dp[i][j] = dp[i - 1][j - 1]

  • Otherwise, choose the cheapest operation:

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

The three candidates represent deletion, insertion, and substitution, respectively.

A bottom-up implementation fills rows in increasing i order and columns in increasing j order. A top-down implementation recursively evaluates the same recurrence with functools.cache.

Code Example

from functools import cache


def edit_distance_top_down(source: str, target: str) -> int:
    """Return the Levenshtein distance using memoized recursion."""

    @cache
    def solve(source_index: int, target_index: int) -> int:
        if source_index == 0:
            return target_index
        if target_index == 0:
            return source_index

        if source[source_index - 1] == target[target_index - 1]:
            return solve(source_index - 1, target_index - 1)

        return 1 + min(
            solve(source_index - 1, target_index),      # Delete
            solve(source_index, target_index - 1),      # Insert
            solve(source_index - 1, target_index - 1),  # Substitute
        )

    return solve(len(source), len(target))


def edit_distance_bottom_up(source: str, target: str) -> int:
    """Return the Levenshtein distance using a bottom-up DP table."""
    source_length = len(source)
    target_length = len(target)
    dp = [[0] * (target_length + 1) for _ in range(source_length + 1)]

    for source_index in range(source_length + 1):
        dp[source_index][0] = source_index

    for target_index in range(target_length + 1):
        dp[0][target_index] = target_index

    for source_index in range(1, source_length + 1):
        for target_index in range(1, target_length + 1):
            if source[source_index - 1] == target[target_index - 1]:
                dp[source_index][target_index] = dp[
                    source_index - 1
                ][target_index - 1]
            else:
                dp[source_index][target_index] = 1 + min(
                    dp[source_index - 1][target_index],
                    dp[source_index][target_index - 1],
                    dp[source_index - 1][target_index - 1],
                )

    return dp[source_length][target_length]


print(edit_distance_top_down("cat", "cut"))     # 1
print(edit_distance_bottom_up("cat", "cut"))    # 1

The main implementation is bottom-up because it avoids recursion-depth issues. Python’s default recursion limit is approximately 1,000, so the top-down version can fail for long strings.

Worked Example

Transforming "cat" into "cut" requires one substitution: replace a with u.

Source prefix Target prefix "" "c" "cu" "cut"
"" 0 1 2 3
"c" 1 0 1 2
"ca" 2 1 1 2
"cat" 3 2 2 1

The final cell, dp[3][3], is 1.

Complexity

For strings of lengths m and n:

  • Bottom-up table

  • Time: Best, average, and worst case are all O(mn) because every table cell is computed.

  • Auxiliary space: O(mn) for the table, excluding the O(m + n) input strings.

  • Top-down memoization

  • Time: Worst case is O(mn); the best case can be O(m + n) when the recursion follows only matching characters.

  • Auxiliary space: Worst case is O(mn) for cached states plus O(m + n) recursion-stack space, excluding the input.

  • Space-optimized bottom-up

  • Each row depends only on the previous row, so auxiliary space can be reduced to O(min(m, n)) by making the shorter string the column dimension.

  • Time remains O(mn).

Common Pitfalls and Interview Tips

  • Initialize both the empty-source and empty-target cases before filling the table.

  • Keep the recurrence orientation consistent: deletion moves up, insertion moves left, and substitution or a match moves diagonally.

  • Python string indexing operates on Unicode code points; this matters only for unusual non-ASCII input.

  • Empty strings and one-character strings are handled by the base cases. Duplicate characters require no special treatment.

  • Negative numbers, sorted-input assumptions, disconnected graphs, and cycles are not applicable to string edit distance.

  • Interviewers commonly ask for reconstruction of the actual edits. Store the chosen operation in each cell and backtrack from dp[m][n].

17

How does dynamic programming solve the word break problem?

Dynamic programming solves the word break problem by identifying prefixes that can be segmented into dictionary words, then reusing each valid prefix to determine whether a longer prefix is also valid.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Let dp[i] mean that the first i characters of text can be segmented into dictionary words. For i > 0, the recurrence is:

dp[i] = True if some j < i satisfies both:

  • dp[j] is true, and

  • text[j:i] is a dictionary word.

The base case is dp[0] = True: the empty prefix is valid. Compute states in increasing order of i, ensuring every required earlier state is already known.

A trie stores the dictionary, allowing candidate words to be extended one character at a time without creating copied substrings.

Recurrence and Properties

The top-down state, can_break(start), asks whether text[start:] can be segmented. Its recurrence considers every dictionary word matching the beginning of that suffix and recursively checks the remaining suffix. Its base case is can_break(len(text)) = True.

Dynamic programming applies because it has:

  • Overlapping subproblems: Different splits can ask whether the same suffix is segmentable.

  • Optimal substructure: A prefix is segmentable exactly when a valid earlier prefix can be followed by one dictionary word.

DP Walkthrough and Comparison

For text = "catsdog" and words = ["cat", "cats", "dog"]:

i Prefix dp[i] Segmentation
0 "" True Empty prefix
1 "c" False No valid first word
2 "ca" False No valid first word
3 "cat" True "cat"
4 "cats" True "cats"
5 "catsd" False No valid continuation
6 "catsdo" False No valid continuation
7 "catsdog" True "cats" + "dog"
Approach Typical time Space When to use
Brute-force backtracking O(n · 2^n + S) O(n + S) Small inputs or conceptual explanation
Top-down with functools.cache O(n² + S) O(n + S) When recursion is easiest to follow
Bottom-up DP O(n² + S) O(n + S) Main implementation; avoids recursion limits

Here, n is the string length and S is the total number of characters in the dictionary.

Code Example

from __future__ import annotations

from collections.abc import Sequence
from dataclasses import dataclass, field
from functools import cache


@dataclass(slots=True)
class TrieNode:
    children: dict[str, TrieNode] = field(default_factory=dict)
    is_word: bool = False


def build_trie(words: Sequence[str]) -> TrieNode:
    root = TrieNode()

    for word in words:
        if not word:
            continue

        node = root
        for character in word:
            child = node.children.get(character)
            if child is None:
                child = TrieNode()
                node.children[character] = child
            node = child

        node.is_word = True

    return root


def word_break_bottom_up(text: str, words: Sequence[str]) -> bool:
    """Return whether text can be segmented into dictionary words."""
    root = build_trie(words)
    length = len(text)

    # dp[end] means text[:end] can be segmented.
    dp = [False] * (length + 1)
    dp[0] = True

    for start in range(length):
        if not dp[start]:
            continue

        node = root
        for end in range(start, length):
            child = node.children.get(text[end])
            if child is None:
                break

            node = child
            if node.is_word:
                dp[end + 1] = True

    return dp[length]


def word_break_top_down(text: str, words: Sequence[str]) -> bool:
    """Return whether text can be segmented using memoized recursion."""
    root = build_trie(words)
    length = len(text)

    @cache
    def can_break(start: int) -> bool:
        if start == length:
            return True

        node = root
        for end in range(start, length):
            child = node.children.get(text[end])
            if child is None:
                break

            node = child
            if node.is_word and can_break(end + 1):
                return True

        return False

    return can_break(0)


print(word_break_bottom_up("catsdog", ["cat", "cats", "dog"]))  # True

Complexity and Edge Cases

Let D be the maximum number of children of a trie node, or 1 if the trie is empty.

  • Best case: Both implementations take O(n + S) when matching paths are constant length; top-down can also finish after matching the entire remaining suffix once.

  • Average/expected case: Both take O(n² + S): there are at most n cached states, each scanning at most n characters, and trie construction processes S characters.

  • Worst case: Python dictionary lookups can take O(D) under adversarial hash collisions, giving O((n² + S)D). Under the usual fixed-alphabet, constant-time child-access model, this is O(n² + S).

  • Space: O(n + S) in all cases, including the trie, DP array or cache, and the top-down recursion stack. The input string and dictionary are not counted.

  • Edge cases: Empty text returns True; an empty dictionary only supports empty text; one-character words work; duplicate dictionary words have no effect. Negative numbers, sorted input, disconnected graphs, and cycles are not applicable.

  • The recursive implementation can exceed Python’s default recursion limit on long inputs. The bottom-up implementation is the main implementation because it avoids recursion.

Common Pitfalls

  • Forgetting the base case dp[0] = True.

  • Confusing “can be segmented” with “must use every dictionary word.”

  • Assuming repeated substrings are optimized without memoization.

  • Using the recursive version on long strings without an iterative alternative.

  • Assuming greedy longest-word selection is safe. For "abcde" with ["ab", "abc", "cd", "e"], greedy chooses "abc" and gets stuck, while "ab" + "cd" + "e" succeeds.

18

Longest increasing subsequence dynamic programming solution

The Longest Increasing Subsequence (LIS) problem finds the length of the longest subsequence whose elements are in strictly increasing order. A dynamic programming solution computes, for every position, the best increasing subsequence ending there.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach and State

For an integer array nums, define dp[i] as the length of the longest strictly increasing subsequence that ends exactly at index i.

This problem has:

  • Overlapping subproblems: Different positions may depend on the same earlier LIS states.

  • Optimal substructure: The best subsequence ending at i is obtained by extending the best valid subsequence ending at an earlier position.

The final answer is the maximum value in dp.

Recurrence and Computation

For each index i, inspect every earlier index j where j < i:

  • If nums[j] < nums[i], append nums[i] to a subsequence ending at j.

  • If at least one such j exists, dp[i] = 1 + max(dp[j]) over those valid indices.

  • Otherwise, dp[i] = 1.

The base case is dp[i] = 1, because every element by itself is an increasing subsequence. The order of computation is increasing index order, from 0 through n - 1, because dp[i] depends only on earlier states.

For the standard O(n²) recurrence, the O(n) table is retained; no two-variable optimization applies because a state may depend on any earlier index.

For nums = [10, 9, 2, 5, 3, 7, 101, 18], the filled table is:

i nums[i] Valid previous indices dp[i]
0 10 none 1
1 9 none 1
2 2 none 1
3 5 2 2
4 3 2 2
5 7 2, 3, 4 3
6 101 0–5 4
7 18 0–5 4

Thus, dp = [1, 1, 1, 2, 2, 3, 4, 4], and the LIS length is 4.

Complexity and Approach Comparison

The input array is not counted in auxiliary space. The top-down implementation includes both its memoization table and its recursion stack.

Approach Time: best/average/worst Auxiliary space When to use
Brute-force enumeration O(2^n) / O(2^n) / O(2^n) O(n) recursion stack Only for small inputs or teaching
Bottom-up DP O(n²) / O(n²) / O(n²) O(n) for dp When directly expressing the recurrence
Top-down DP O(n²) / O(n²) / O(n²) O(n) cache plus O(n) stack When a recursive formulation is useful
Patience sorting with binary search O(n log n) / O(n log n) / O(n log n) O(n) for tails Large inputs; fastest comparison-based approach

The bottom-up implementation checks i earlier positions for each element. The top-down implementation performs the same total number of state checks but stores results in a functools.cache. In the O(n log n) approach, tails[k] is the smallest possible tail of an increasing subsequence of length k + 1.

Code Example

The main implementation is the bottom-up DP solution. The top-down DP and optimal binary-search implementations are included for comparison.

from bisect import bisect_left
from functools import cache


def length_of_lis_bottom_up(nums: list[int]) -> int:
    """Return the length of the longest strictly increasing subsequence."""
    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)


def length_of_lis_top_down(nums: list[int]) -> int:
    """Return the LIS length using memoized recursion."""
    if not nums:
        return 0

    @cache
    def lis_ending_at(index: int) -> int:
        best = 1
        for j in range(index):
            if nums[j] < nums[index]:
                best = max(best, lis_ending_at(j) + 1)
        return best

    return max(lis_ending_at(index) for index in range(len(nums)))


def length_of_lis_nlogn(nums: list[int]) -> int:
    """Return the LIS length using binary search and a tails array."""
    tails: list[int] = []

    for value in nums:
        position = bisect_left(tails, value)
        if position == len(tails):
            tails.append(value)
        else:
            tails[position] = value

    return len(tails)


if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    print(length_of_lis_bottom_up(nums))  # 4
    print(length_of_lis_top_down(nums))   # 4
    print(length_of_lis_nlogn(nums))      # 4

Interview Tips

  • Empty input: Return 0; a single element returns 1.

  • Duplicates: Use <, not <=, for a strictly increasing subsequence. Change the comparison to <= for a longest non-decreasing subsequence.

  • Negative numbers: They require no special handling; only relative ordering matters.

  • Already sorted input: The answer is n; descending input has an answer of 1.

  • Common pitfalls: Use max(dp), not dp[-1], and avoid off-by-one errors in the tails index.

  • Recursion depth: The top-down version can approach Python’s default recursion limit for large inputs; prefer the iterative implementation.

  • Mutation and graph concerns: These implementations do not mutate the input. Visited sets, disconnected graphs, and cycles are not applicable to LIS.

  • Common follow-up: Reconstruct the subsequence by storing predecessor indices, or explain the O(n log n) tails method.

19

How to solve maximum sum increasing subsequence with DP

The Maximum Sum Increasing Subsequence problem finds the largest possible sum of a strictly increasing subsequence in an array. It is solved with dynamic programming by storing the best sum ending at each index and extending it to later, larger values.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Problem Definition

  • State: dp[i] is the maximum sum of a strictly increasing subsequence that ends at index i.

  • Recurrence: dp[i] = max(arr[i], max(dp[j] + arr[i]) for j < i where arr[j] < arr[i]).

  • Base case: dp[0] = arr[0].

  • Result: max(dp) over all indices.

How It Works

  • Optimal substructure: the best subsequence ending at i uses the best subsequence ending at some earlier j.

  • Overlapping subproblems: many increasing subsequences share prefixes, so recomputing them is wasteful.

  • Order: compute dp[i] for i from 1 to n-1, because each value depends only on earlier indices.

  • Recurrence options: for each i, either start a new subsequence with arr[i] or extend the best subsequence ending at some j < i where arr[j] < arr[i].

DP Table Example

For arr = [1, 101, 2, 3, 100, 4, 5]:

i arr[i] dp[i]
0 1 1
1 101 102
2 2 3
3 3 6
4 100 106
5 4 10
6 5 15

The table shows how each dp[i] is built from previous values, and the final answer is the maximum entry.

Code Example

The main implementation is bottom-up. A top-down version can use recursion with functools.cache, but the iterative table is preferred to avoid recursion depth limits.

def max_sum_increasing_subsequence(arr: list[int]) -> int:
    """Return the maximum sum of a strictly increasing subsequence.

    Uses dynamic programming with a bottom-up table.
    """
    if not arr:
        return 0
    n = len(arr)
    dp = [0] * n
    dp[0] = arr[0]
    for i in range(1, n):
        dp[i] = arr[i]
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + arr[i] > dp[i]:
                dp[i] = dp[j] + arr[i]
    return max(dp)

# Example: max_sum_increasing_subsequence([1, 101, 2, 3, 100, 4, 5])  # Output: 106

Complexity and Pitfalls

  • Time: O(n^2) because of the nested loops over all pairs (j, i). This is best, average, and worst case, as the loops always run regardless of input order.

  • Space: O(n) for the dp array; the input is not counted.

  • Edge cases: empty input returns 0, single element returns itself, duplicates are excluded by strict inequality, negative numbers are handled by initializing dp[i] = arr[i].

  • Common pitfalls: forgetting to take max(dp) instead of dp[n-1], using non-strict inequality, and mutating the input array.

  • Follow-up: interviewers often ask for the actual subsequence, not just the sum, which requires tracking predecessors.

20

How do I count array subsequences with a given sum?

Dynamic programming counts subsequences by deciding whether to include each array element. This implementation counts subsequences by their selected indices, so duplicate values can produce multiple subsequences, and the empty subsequence is counted when the target is 0.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

State, Recurrence, and Computation Order

Let dp[i][s] mean the number of subsequences selected from the first i elements whose sum is s.

For the next value a[i - 1], every subsequence either:

  • Excludes it: contributes dp[i - 1][s].

  • Includes it: contributes dp[i - 1][s - a[i - 1]], when that sum exists.

Therefore:

dp[i][s] = dp[i - 1][s] + dp[i - 1][s - a[i - 1]]

The base cases are:

  • dp[0][0] = 1, representing the empty subsequence.

  • dp[0][s] = 0 for every s != 0.

  • The final answer is dp[n][target].

States are computed in increasing order of i. The bottom-up implementation stores only the current and previous rows as dictionaries, allowing negative integers as well.

The two properties that make dynamic programming applicable are:

  • Overlapping subproblems: multiple paths reach the same (index, remaining_sum) state.

  • Optimal substructure: each state can be solved by combining the answers for excluding and including the current element.

Example DP Table

For values = [1, 2, 3], the states after processing each prefix are:

Elements processed Sum 0 Sum 1 Sum 2 Sum 3 Sum 4 Sum 5 Sum 6
None 1 0 0 0 0 0 0
[1] 1 1 0 0 0 0 0
[1, 2] 1 1 1 1 0 0 0
[1, 2, 3] 1 1 1 2 1 1 1

For target 3, the two subsequences are [3] and [1, 2].

Code Example

The main implementation uses the iterative bottom-up approach. The top-down version demonstrates the same recurrence using functools.cache.

from collections.abc import Sequence
from functools import cache


def count_subsequences_top_down(values: Sequence[int], target: int) -> int:
    """Count index-distinct subsequences whose values sum to target."""
    @cache
    def count(index: int, remaining_sum: int) -> int:
        if index == len(values):
            return 1 if remaining_sum == 0 else 0

        exclude = count(index + 1, remaining_sum)
        include = count(index + 1, remaining_sum - values[index])
        return exclude + include

    return count(0, target)


def count_subsequences_bottom_up(values: Sequence[int], target: int) -> int:
    """Count index-distinct subsequences whose values sum to target."""
    counts: dict[int, int] = {0: 1}

    for value in values:
        # Copying prevents the current element from being reused.
        next_counts = counts.copy()

        for subtotal, ways in counts.items():
            new_sum = subtotal + value
            next_counts[new_sum] = next_counts.get(new_sum, 0) + ways

        counts = next_counts

    return counts.get(target, 0)


print(count_subsequences_top_down([1, 2, 3], 3))    # 2
print(count_subsequences_bottom_up([1, 2, 3], 3))  # 2

Complexity

Let n be the number of elements and R the maximum number of distinct reachable sums in a DP row.

Approach Best time Average time Worst time Auxiliary space
Top-down O(nR) O(nR) O(n²R²) under pathological hash collisions O(nR) for memoization plus O(n) recursion stack
Bottom-up O(nR) O(nR) O(nR²) under pathological hash collisions O® for the current and next rows

These bounds assume average O(1) dictionary operations. Space is auxiliary and does not count the input. With arbitrary negative values, R can grow exponentially; for nonnegative values, a target-bounded array implementation can achieve O(n × target) time and O(target) space.

Edge Cases

  • Empty input: returns 1 for target 0, otherwise 0.

  • One element: correctly counts whether that element alone matches.

  • Duplicates: [1, 1] with target 1 returns 2 because the indices differ.

  • Negative numbers: supported by both implementations.

  • Target 0: includes the empty subsequence; subtract 1 if only non-empty subsequences are allowed.

  • No matching subset: returns 0.

  • Sorted or unsorted input: produces the same count because order is irrelevant to the sum.

Common Pitfalls

  • Updating the same dictionary in place can reuse an element multiple times.

  • Counting by value rather than by selected indices changes the intended definition.

  • The recursive solution uses O(n) stack depth and may exceed Python’s default recursion limit for large inputs; prefer the bottom-up version.

  • Counts can become very large. If a modulus is required, apply it consistently after every addition.

  • Interviewers commonly ask about empty subsequences, duplicate values, negative inputs, and whether they want distinct value sequences rather than distinct index selections.

21

How does Dynamic Programming solve the equal partition subset sum problem?

The partition equal subset sum problem asks whether a set of numbers can be divided into two non-empty subsets with equal sums. Dynamic Programming efficiently determines this by tracking which subset sums can be formed.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let total be the sum of all numbers:

  • If total is odd, an equal partition is impossible.

  • Otherwise, the problem becomes finding a subset whose sum is target = total // 2.

  • If such a subset exists, the remaining elements automatically have the same sum.

The main implementation uses bottom-up dynamic programming. A top-down implementation using functools.cache is also included for comparison.

State, Recurrence, and Base Cases

For the bottom-up solution, dp[s] means:

True if a subset of the elements processed so far can produce sum s.

For each number value, the recurrence is:

new_dp[s] = old_dp[s] OR (s >= value AND old_dp[s - value])

Base case:

  • dp[0] = True, because the empty subset produces sum zero.

  • All other states initially equal False.

Elements are processed one at a time, and sums are updated from target down to value. Descending order ensures each element is used at most once, making this a 0/1 subset sum problem.

The top-down state can_make(index, remaining) asks whether elements starting at index can produce remaining:

  • If remaining == 0, return True.

  • If no elements remain, return False.

  • Otherwise, exclude the current element or include it when its value does not exceed remaining.

Why Dynamic Programming Applies

Dynamic Programming is suitable because partition problems have:

  • Overlapping subproblems: Many combinations of elements repeatedly ask whether the same remaining sum can be formed.

  • Optimal substructure: A sum is reachable if the sum was already reachable without the current element, or if the smaller remaining sum can be completed using the current element.

Memoization prevents the top-down version from solving the same state repeatedly.

Worked Example

For [1, 2, 3, 6], the total is 12, so the target is 6.

Processed elements 0 1 2 3 4 5 6
None T F F F F F F
1 T T F F F F F
1, 2 T T T T F F F
1, 2, 3 T T T T T T T
1, 2, 3, 6 T T T T T T T

Since dp[6] is True, one partition is {1, 2, 3} and {6}.

Complexity and Alternatives

Let n be the number of elements and T = total // 2.

Approach Time Auxiliary space When to use
Brute-force subsets O(2^n) O(n) Very small inputs
Top-down with cache Best O(n); average/worst O(nT) Worst O(nT) for cache and O(n) stack Recursive state exploration
Bottom-up table Best/average/worst O(nT) O(T) General-purpose solution

The bottom-up runtime is O(nT) because every element may update every possible sum. Its auxiliary space is O(T), excluding the input. A conceptual two-dimensional table would require O(nT) space; updating one array in descending order compresses it to O(T).

For the broader minimum-difference partition problem, find the largest reachable sum s <= total // 2; the minimum difference is total - 2s.

Code Example

from functools import cache


def can_partition_top_down(numbers: list[int]) -> bool:
    """Return whether numbers can form two non-empty equal-sum subsets."""
    if len(numbers) < 2:
        return False
    if any(number < 0 for number in numbers):
        raise ValueError("Partition inputs must contain non-negative integers.")

    total = sum(numbers)
    if total % 2 != 0:
        return False

    target = total // 2

    @cache
    def can_make(index: int, remaining: int) -> bool:
        if remaining == 0:
            return True
        if index == len(numbers):
            return False

        value = numbers[index]
        exclude = can_make(index + 1, remaining)
        include = (
            value <= remaining
            and can_make(index + 1, remaining - value)
        )
        return exclude or include

    return can_make(0, target)


def can_partition_bottom_up(numbers: list[int]) -> bool:
    """Return whether numbers can form two non-empty equal-sum subsets."""
    if len(numbers) < 2:
        return False
    if any(number < 0 for number in numbers):
        raise ValueError("Partition inputs must contain non-negative integers.")

    total = sum(numbers)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for value in numbers:
        # Descending order prevents using this element more than once.
        for current_sum in range(target, value - 1, -1):
            if dp[current_sum - value]:
                dp[current_sum] = True

    return dp[target]


numbers = [1, 5, 11, 5]
print(can_partition_top_down(numbers))    # True
print(can_partition_bottom_up(numbers))  # True

Common Pitfalls

  • Updating sums in ascending order: This can reuse an element and incorrectly solve an unbounded variant.

  • Ignoring empty or single-element inputs: The implementation requires two non-empty subsets and returns False for these cases.

  • Negative numbers: The shown solution assumes non-negative integers and raises ValueError otherwise.

  • Duplicates: Each occurrence is treated as a separate element, which is correct for multisets.

  • Recursion depth: The top-down version may exceed Python’s default recursion limit for more than roughly 1,000 elements; use the bottom-up version.

  • Large target values: The O(nT) runtime is pseudo-polynomial because it depends on the numeric target rather than only the number of elements.

  • Follow-up questions: Interviewers commonly ask how to reconstruct the actual subsets or how to solve the minimum-difference variant.

22

How do I solve the subset sum problem using dynamic programming?

A dynamic programming solution records which sums can be formed from each prefix of the input, avoiding repeated enumeration of equivalent subsets. For the standard version, all values and the target are nonnegative, and each input element may be selected at most once.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

DP Model

Let dp[i][s] mean: a subset of the first i elements can produce sum s.

For a value v_i, the recurrence is:

dp[i][s] = dp[i - 1][s] OR dp[i - 1][s - v_i]

The first term excludes v_i; the second includes it.

Base cases:

  • dp[0][0] = True: the empty subset produces sum zero.

  • dp[0][s] = False for every s > 0.

  • The answer is dp[n][target].

Rows are computed in increasing order of i. When compressing the table into one array, sums are processed downward so the current element cannot be reused.

The two defining properties are:

  • Overlapping subproblems: many candidate subsets reach the same (i, s) state.

  • Optimal substructure: a sum is reachable if either the prefix without the current element or the appropriate earlier prefix containing it reaches that sum.

Top-Down and Bottom-Up

The top-down state is can_make(index, remaining): whether elements from index onward can form remaining. Its recurrence is can_make(index + 1, remaining) OR can_make(index + 1, remaining - values[index]).

Its base cases are:

  • If remaining == 0, return True; the empty suffix completes the subset.

  • If the input is exhausted while remaining != 0, return False.

The bottom-up solution uses a one-dimensional reachable array. It keeps only the previous row, reducing auxiliary space from O(nT) to O(T) for target T. The main implementation below is iterative.

Code Example

from collections.abc import Sequence
from functools import cache


def subset_sum_top_down(values: Sequence[int], target: int) -> bool:
    """Return whether a subset of values sums exactly to target."""
    @cache
    def can_make(index: int, remaining: int) -> bool:
        if remaining == 0:
            return True
        if index == len(values):
            return False

        return (
            can_make(index + 1, remaining)
            or can_make(index + 1, remaining - values[index])
        )

    return can_make(0, target)


def subset_sum_bottom_up(values: Sequence[int], target: int) -> bool:
    """Return whether a subset of values sums exactly to target."""
    if all(value >= 0 for value in values):
        if target < 0:
            return False

        reachable = [False] * (target + 1)
        reachable[0] = True

        for value in values:
            if value > target:
                continue

            # Descending order prevents using this element more than once.
            for total in range(target, value - 1, -1):
                if reachable[total - value]:
                    reachable[total] = True

        return reachable[target]

    # Signed-value extension: index sums using an offset for negative sums.
    negative_sum = sum(value for value in values if value < 0)
    positive_sum = sum(value for value in values if value > 0)

    if not negative_sum <= target <= positive_sum:
        return False

    width = positive_sum - negative_sum + 1
    reachable = [False] * width
    reachable[-negative_sum] = True

    for value in values:
        if value > 0:
            # Descending: the lower source has not used this value yet.
            for index in range(width - 1, -1, -1):
                source = index - value
                if source >= 0 and reachable[source]:
                    reachable[index] = True
        elif value < 0:
            # Ascending: the higher source has not used this value yet.
            for index in range(width):
                source = index - value
                if source < width and reachable[source]:
                    reachable[index] = True

    return reachable[target - negative_sum]


print(subset_sum_top_down([3, 2, 5], 7))      # True
print(subset_sum_bottom_up([3, 2, 5], 7))     # True

Worked Example

For values = [3, 2, 5] and target = 7:

Items processed 0 1 2 3 4 5 6 7
None T F F F F F F F
[3] T F F T F F F F
[3, 2] T F T T F T F F
[3, 2, 5] T F T T F T F T

The final sum 7 is reachable because 2 + 5 = 7.

Complexity

Let n be the number of elements, T the nonnegative target, and R = 1 + sum(abs(value)) the possible sum-range width for signed inputs.

Approach Best time Average time Worst time Auxiliary space Use
Full subset enumeration O(2^n) O(2^n) O(2^n) O(n) stack Baseline without DP
Bottom-up, nonnegative O(n) O(n(T+1)) O(n(T+1)) O(T+1) Standard subset sum
Top-down, nonnegative O(n) O(n(T+1)) O(n(T+1)) O(n(T+1)) cache plus O(n) stack Explores reachable states only
Bottom-up, signed O(nR) O(nR) O(nR) O(R) Negative values allowed
Top-down, signed O(nR) O(nR) O(nR) O(nR) cache plus O(n) stack Negative values with memoization

The average bounds assume values distributed uniformly within the relevant range; average time is otherwise distribution-dependent. These bounds exclude the input itself. The top-down recursion can exceed Python’s default recursion limit for very large inputs; use the iterative version or an explicit stack in that case.

Common Pitfalls and Interview Tips

  • Processing sums upward in the nonnegative DP incorrectly allows one element to be reused.

  • Duplicate values are separate elements and may both be selected.

  • Target 0 is always reachable through the empty subset; an empty input does not reach a positive target.

  • With one element, only target 0 or that element’s value is reachable.

  • Already sorted input has the same result; sorting is unnecessary.

  • Negative values invalidate the simple 0..T table, so use the signed-value extension or a reachable-sum set.

  • Input order does not affect the answer, and the implementations do not mutate the input.

  • In fixed-width languages, avoid integer overflow when calculating sum bounds.

  • Common follow-ups include reconstructing an actual subset, counting valid subsets, and handling unlimited-use coin change.

23

How to solve Balanced Partition using dynamic programming

The Balanced Partition problem is solved with dynamic programming by finding the subset sum closest to half the total sum, then computing the minimum difference between the two subsets.

Read full answer

Applies toPython 3.12

Problem Definition

Given an array of integers, split it into two subsets so the absolute difference of their sums is minimized. If the total sum is odd, the minimum difference is at least 1.

How It Works

The key insight is that minimizing the difference is equivalent to maximizing a subset sum S such that S <= total_sum / 2. The other subset then has sum total_sum - S, and the difference is total_sum - 2 * S.

State: dp[j] is True if a subset of the processed numbers sums exactly to j.

Recurrence: For each number num, update dp[j] = dp[j] or dp[j - num] for j from target down to num.

Base case: dp[0] = True (empty subset sums to 0).

Order: Process each number once, updating the DP array from high to low to avoid reusing the same number.

Complexity: Time is O(n * S) where n is the number of elements and S is the total sum. Space is O(S) for the 1D boolean array.

Top-Down vs Bottom-Up

  • Top-down: Recursion with functools.lru_cache memoizes can_sum(j, i), checking if sum j is possible using elements up to index i. Space is O(n * S) for the memoization table plus O(n) recursion stack.

  • Bottom-up: Iteratively fills a 1D boolean array. The main code below uses the bottom-up approach.

Filled DP Table Example for nums = [1, 2, 3], total = 6, target = 3:

Step dp[0] dp[1] dp[2] dp[3]
Init True False False False
Add 1 True True False False
Add 2 True True True True
Add 3 True True True True

The largest reachable sum is 3, so the minimum difference is 6 - 2 * 3 = 0.

Code Example

from functools import lru_cache

def balanced_partition(nums: list[int]) -> int:
    """Return the minimum difference between two subset sums."""
    total = sum(nums)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            if dp[j - num]:
                dp[j] = True
    for j in range(target, -1, -1):
        if dp[j]:
            return total - 2 * j
    return total

def balanced_partition_top_down(nums: list[int]) -> int:
    """Alternative top-down approach with memoization."""
    total = sum(nums)
    target = total // 2

    @lru_cache(maxsize=None)
    def can_sum(j: int, i: int) -> bool:
        if j == 0:
            return True
        if j < 0 or i < 0:
            return False
        return can_sum(j, i - 1) or can_sum(j - nums[i], i - 1)

    for j in range(target, -1, -1):
        if can_sum(j, len(nums) - 1):
            return total - 2 * j
    return total

# Example: balanced_partition([1, 2, 3, 4, 5]) -> 1

Common Pitfalls

  • Negative numbers: The DP assumes non-negative integers. If negatives exist, the sum range shifts and the approach needs adjustment.

  • Odd total sum: The minimum difference cannot be 0; the algorithm still works but returns at least 1.

  • Large sums: If the total sum is very large, the DP array may become too big; consider a set-based approach or meet-in-the-middle.

  • Off-by-one errors: The inner loop must go from target down to num, not up.

24

How do you solve unique paths with obstacles using DP?

To find the number of unique paths from the top-left to the bottom-right corner of a grid containing obstacles, use dynamic programming to build a table of subproblem solutions. The key insight is that a cell can only be reached from above or from the left, so the total paths to a cell is the sum of paths to those two neighbors.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The problem exhibits two required properties: - Overlapping subproblems: Many cells share the same predecessors, so a naive recursion recomputes the same values repeatedly. - Optimal substructure: The number of paths to a cell (i, j) is determined entirely by the counts of its top and left neighbors.

Define the state as dp[i][j], the number of unique paths to reach cell (i, j) starting from (0, 0). The recurrence relation is: - If grid[i][j] == 1 (obstacle): dp[i][j] = 0 - If grid[i][j] == 0 (empty): dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base cases: dp[0][0] = 1 if the start is not an obstacle. Cells in the first row and first column are reachable only from their left or top neighbor respectively, so they inherit that value unless blocked.

Step-by-step walkthrough for grid = [[0,0,0],[0,1,0],[0,0,0]]: 1. Initialize dp[0][0] = 1. 2. Fill first row: dp[0][1] = 1 (from left), dp[0][2] = 1 (from left). 3. Fill second row: dp[1][0] = 1 (from top), dp[1][1] = 0 (obstacle), dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1. 4. Fill third row: dp[2][0] = 1 (from top), dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1, dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2.

Filled DP table:

i j 0 1 2
0 1 1 1
1 1 0 1
2 1 1 2

Code Example

The bottom-up approach is preferred for interviews as it avoids recursion overhead and recursion-depth limits.

from typing import List

def unique_paths_with_obstacles(grid: List[List[int]]) -> int:
    """
    Returns the number of unique paths from top-left to bottom-right
    in a grid where 1 is an obstacle and 0 is an empty space.
    """
    if not grid or not grid[0]:
        return 0
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[m - 1][n - 1] == 1:
        return 0

    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[i][j] = 0
                continue
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if j > 0:
                dp[i][j] += dp[i][j - 1]

    return dp[m - 1][n - 1]

# Example: grid = [[0,0,0],[0,1,0],[0,0,0]] -> Output: 2

Top-down recursion with caching is an alternative (note: recursion depth may exceed Python’s default limit for large grids; use sys.setrecursionlimit or an explicit stack if needed):

from functools import cache
from typing import List

def unique_paths_top_down(grid: List[List[int]]) -> int:
    if not grid or not grid[0] or grid[0][0] == 1:
        return 0
    m, n = len(grid), len(grid[0])

    @cache
    def count_paths(i: int, j: int) -> int:
        if i < 0 or j < 0 or grid[i][j] == 1:
            return 0
        if i == 0 and j == 0:
            return 1
        return count_paths(i - 1, j) + count_paths(i, j - 1)

    return count_paths(m - 1, n - 1)

Complexity and Approaches Comparison

Approach Time Complexity Space Complexity When to Use
Brute Force (Recursion) $O(2^{m+n})$ $O(m+n)$ stack Small grids only
Bottom-Up DP $O(m times n)$ $O(m times n)$ Standard solution
Top-Down DP $O(m times n)$ $O(m times n)$ cache + $O(m+n)$ stack When recursion is natural
  • Time: $O(m times n)$ best, average, and worst case for both DP approaches. Every cell is visited exactly once.

  • Space: $O(m times n)$ for the 2D table, or $O(n)$ with the 1D optimization (see below). The top-down approach uses $O(m times n)$ for the cache plus $O(m+n)$ for the recursion stack. Input storage is not counted.

Space Optimization

You can reduce space to $O(n)$ by using a 1D array dp of size n. Since dp[i][j] depends only on the current row’s left cell and the previous row’s same column, update the array left-to-right: dp[j] = dp[j] + dp[j-1] (with dp[0] reset to 0 if the current cell is an obstacle).

Common Pitfalls

  • Forgetting to check if the start or end cell is an obstacle, which makes the answer 0.

  • Off-by-one errors when accessing dp[i-1] or dp[j-1] at the boundaries.

  • Mutating the input grid to store DP values instead of using a separate table.

  • Interviewers often ask how to handle a grid where the start is blocked or how to print the actual path, not just the count.

  • For the top-down approach, recursion depth can exceed Python’s default limit (≈1000) for large grids; consider raising the limit or using an iterative solution.

25

How does dynamic programming solve minimum-cost grid paths?

Dynamic Programming solves the minimum-cost path problem by reusing the best result for each grid cell. Assuming movement is allowed only right or down, the optimal cost to reach a cell is its own cost plus the cheaper optimal cost of the cell above or to its left.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How DP Works

Define the state as:

  • dp[i][j]: the minimum total cost to reach cell (i, j) from (0, 0), including the cost of that cell.

The recurrence is:

dp[i][j] = cost[i][j] + min(dp[i - 1][j], dp[i][j - 1])

Base cases and boundary rules:

  • dp[0][0] = cost[0][0].

  • The first row can only be reached from the left.

  • The first column can only be reached from above.

  • An out-of-bounds predecessor is treated as infinity.

Bottom-up computation processes rows from top to bottom and columns from left to right. At each cell, the value above has already been computed, and the value to the left is available in the current row.

Dynamic Programming applies because this problem has:

  • Overlapping subproblems: many paths pass through the same cells, so the optimal cost for each cell is repeatedly needed.

  • Optimal substructure: an optimal path to a cell must use an optimal path to one of its valid predecessors.

Brute-Force vs. Dynamic Programming

Approach Time Space When to use
Brute-force (DFS all paths) O(2^(m+n)) O(m+n) recursion stack Only for tiny grids or understanding
Dynamic Programming (bottom-up) O(mn) O(n) optimized Standard solution for all grid sizes

Top-Down and Bottom-Up

Approach Time Auxiliary space When to use
Top-down with functools.cache O(mn) O(mn) memoization plus O(m+n) recursion stack Closely mirrors the recurrence and explores only reachable states
Bottom-up with a table O(mn) O(mn) for the full table Straightforward implementation without recursion
Bottom-up with one row O(mn) O(n) Preferred production solution when only the minimum cost is needed

The main implementation below uses the bottom-up approach and optimizes space to one row.

Example Walkthrough

For the cost grid:

[[1, 3, 1], [1, 5, 1], [4, 2, 3]]

The filled DP table is:

dp[i][j] Column 0 Column 1 Column 2
Row 0 1 4 5
Row 1 2 7 6
Row 2 6 8 9

For example, dp[2][2] = 3 + min(dp[1][2], dp[2][1]) = 3 + min(6, 8) = 9. One optimal path has cell costs 1 + 3 + 1 + 1 + 3 = 9.

Code Example

from functools import cache


def _validate_grid(grid: list[list[int]]) -> tuple[int, int]:
    """Return grid dimensions, rejecting empty or ragged grids."""
    if not grid or not grid[0]:
        raise ValueError("The grid must contain at least one cell.")

    width = len(grid[0])
    if any(len(row) != width for row in grid):
        raise ValueError("The grid must be rectangular.")

    return len(grid), width


def min_cost_top_down(grid: list[list[int]]) -> int:
    """Return the minimum right/down path cost from top-left to bottom-right."""
    rows, columns = _validate_grid(grid)

    @cache
    def dp(row: int, column: int) -> int:
        if row == rows - 1 and column == columns - 1:
            return grid[row][column]

        best_next = min(
            dp(row + 1, column) if row + 1 < rows else float("inf"),
            dp(row, column + 1) if column + 1 < columns else float("inf"),
        )
        return grid[row][column] + int(best_next)

    return dp(0, 0)


def min_cost_bottom_up(grid: list[list[int]]) -> int:
    """Return the minimum right/down path cost using one DP row."""
    rows, columns = _validate_grid(grid)
    dp = [0] * columns
    dp[0] = grid[0][0]

    # The first row can only be reached by moving right.
    for column in range(1, columns):
        dp[column] = dp[column - 1] + grid[0][column]

    for row in range(1, rows):
        # The first column can only be reached by moving down.
        dp[0] += grid[row][0]

        for column in range(1, columns):
            # Before assignment, dp[column] is the value from the row above.
            # dp[column - 1] is the value from the current row.
            dp[column] = grid[row][column] + min(
                dp[column], dp[column - 1]
            )

    return dp[-1]


grid = [[1, 3, 1], [1, 5, 1], [4, 2, 3]]
print(min_cost_top_down(grid))    # 9
print(min_cost_bottom_up(grid))   # 9

Complexity and Edge Cases

  • Time: O(mn) in the best, average, and worst cases. Each cell is processed once.

  • Top-down space: O(mn) auxiliary space for cached states and O(m+n) recursion-stack space, excluding the O(mn) input grid.

  • Bottom-up space: O(n) auxiliary space, excluding the O(mn) input grid; O(mn) total space if the input is counted.

  • An empty grid raises ValueError; a one-cell grid returns that cell’s cost.

  • Duplicate and negative cell costs do not affect correctness under right/down movement because the grid forms a directed acyclic graph.

  • The recursive solution can exceed Python’s default recursion limit on large grids; the iterative bottom-up version avoids this issue.

Common Pitfalls

  • Off-by-one errors: Handle the starting cell separately and avoid accessing negative predecessor indices.

  • Boundary errors: The first row and first column have only one valid predecessor.

  • Recursion depth: Prefer bottom-up DP for grids with more than roughly 1,000 cells along a path.

  • Integer overflow: In languages such as Java or C++, use a sufficiently wide integer type for large path totals.

  • Input mutation: The implementation does not modify the grid.

  • Path reconstruction: To recover the path, store which predecessor was selected for each cell, then backtrack from the bottom-right cell. A visited set is unnecessary because right/down movement cannot create cycles.

Interviewers commonly follow up by asking for path reconstruction, support for up/left/right/down movement, or the reason Dijkstra’s algorithm is unnecessary for this restricted version.

26

Maximum-sum path in a matrix with right and down moves

The standard matrix-path problem is solved with dynamic programming: compute the best sum obtainable from each cell and reuse those results instead of enumerating exponentially many paths. This answer assumes moves are only right or down, cells cannot be revisited, and the path may start and end at any cell.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Model and DP State

Let dp[row][column] represent the maximum sum of a valid path that starts at (row, column).

The recurrence is:

dp[row][column] = matrix[row][column] + max(0, dp[row + 1][column], dp[row][column + 1])

  • The 0 allows the path to stop at the current cell.

  • Neighbors outside the matrix are ignored.

  • The final answer is the maximum value in dp.

This approach relies on two properties:

  • Overlapping subproblems: multiple paths request the best continuation from the same cell.

  • Optimal substructure: the best path from a cell consists of that cell plus the best valid continuation.

If the path must start at the top-left and finish at the bottom-right, remove the 0 stop option and return dp[0][0].

Computation Order and Worked Example

Compute cells from bottom-right toward top-left so that the lower and right-hand results are already available.

For:

1  2  3
4  5  6
7  8  9

The filled DP table is:

Row Column 0 1 2
0 29 24 18
1 28 22 15
2 24 17 9
  1. dp[2][2] = 9.

  2. dp[2][1] = 8 + max(0, 9) = 17.

  3. dp[1][1] = 5 + max(0, 17, 15) = 22.

  4. dp[0][0] = 1 + max(0, 28, 24) = 29.

The best path is 1 → 4 → 7 → 8 → 9, with sum 29.

Code Example

The main implementation below uses the bottom-up table. The top-down version uses functools.cache to demonstrate the equivalent recursive formulation.

from functools import cache

Matrix = list[list[int]]


def longest_path_top_down(matrix: Matrix) -> int:
    """Return the maximum sum of a right/down path starting at any cell."""
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    columns = len(matrix[0])
    if any(len(row) != columns for row in matrix):
        raise ValueError("Matrix rows must all have the same length")

    @cache
    def best_from(row: int, column: int) -> int:
        continuation = 0

        if row + 1 < rows:
            continuation = max(continuation, best_from(row + 1, column))

        if column + 1 < columns:
            continuation = max(continuation, best_from(row, column + 1))

        return matrix[row][column] + continuation

    return max(
        best_from(row, column)
        for row in range(rows)
        for column in range(columns)
    )


def longest_path_bottom_up(matrix: Matrix) -> int:
    """Return the maximum sum of a right/down path starting at any cell."""
    if not matrix or not matrix[0]:
        return 0

    rows = len(matrix)
    columns = len(matrix[0])
    if any(len(row) != columns for row in matrix):
        raise ValueError("Matrix rows must all have the same length")

    dp = [[0] * columns for _ in range(rows)]

    for row in range(rows - 1, -1, -1):
        for column in range(columns - 1, -1, -1):
            continuation = 0

            if row + 1 < rows:
                continuation = max(continuation, dp[row + 1][column])

            if column + 1 < columns:
                continuation = max(continuation, dp[row][column + 1])

            dp[row][column] = matrix[row][column] + continuation

    return max(max(row) for row in dp)


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

print(longest_path_top_down(matrix))   # 29
print(longest_path_bottom_up(matrix))  # 29

Complexity and Optimization

Let m be the number of rows and n the number of columns. Auxiliary space excludes the input matrix.

Approach Time Auxiliary space When to use
Brute-force path enumeration O(2^(m+n)) worst case O(m+n) recursion stack Only for very small matrices
Memoized top-down DP O(mn) O(mn) cache plus O(m+n) stack When the recursive formulation is clearest
Bottom-up DP table O(mn) O(mn) General-purpose solution
One-row bottom-up DP O(mn) O(n) When memory usage must be reduced

The DP time is O(mn) because each cell is processed once. Its space is O(mn) because the table stores one result per cell.

The one-row optimization is also O(mn) in time and O(n) in auxiliary space. It overwrites values for the next row while retaining the current row’s right-hand result.

Common Pitfalls

  • Undefined movement rules: If moves can go in all four directions, finding the longest non-repeating path is generally NP-hard; right/down DP is not sufficient.

  • Negative values: The 0 continuation correctly allows a path to stop. For a one-cell negative matrix, the result remains that negative value.

  • Empty matrix: The implementation returns 0 as a conventional result.

  • Recursion depth: The top-down solution can exceed Python’s default recursion limit for large matrices; prefer bottom-up DP.

  • Fixed endpoints: Keep the 0 stop option only when the path may end anywhere.

  • Duplicates or sorted rows: Neither changes the recurrence; matrix position determines legal moves.

  • Cycles or disconnected graphs: These do not occur with right/down-only movement.

  • Integer overflow: Python integers do not overflow; use an appropriate wide integer type in languages such as Java or C++.

  • Common follow-up: Interviewers often ask how to support obstacles, fixed start/end cells, or O(n)-space optimization.

27

How does dynamic programming solve the word wrap problem?

The classic word wrap problem uses dynamic programming to choose line breaks that minimize the total penalty from unused space. Each non-final line costs the square of its unused width, while the final line has no penalty.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

DP Formulation

Assume the words must remain in their original order, each line has maximum width width, and the penalty for a non-final line of length length is:

(width - length) ** 2

  • State: dp[i] is the minimum penalty for wrapping words starting at index i through the end.

  • Base case: dp[n] = 0, because no words remain.

  • Recurrence: Try every final word j that can fit on the current line:

dp[i] = min(cost(i, j) + dp[j + 1])

  • cost(i, j) is 0 when j is the last word; otherwise, it is the square of the unused width.

  • Bottom-up order: Compute dp[i] from dp[n - 1] down to dp[0].

  • Top-down order: Evaluate the same recurrence using recursion and functools.cache.

This works because the problem has overlapping subproblems, since many line choices reuse the same suffix states, and optimal substructure, since the best solution for a suffix can be appended to any valid current line.

Worked Example

For ["a", "b", "c", "d"] with width = 3, the optimal result is ["a b", "c d"], with penalty 0.

State i Candidate transitions dp[i] Selected line
4 Base case 0 —
3 "d" 0 d
2 "c d" 0 c d
1 "b c" gives 0; "b" gives 4 0 b c
0 "a b" gives 0; "a" gives 4 0 a b

Complexity Comparison

Approach Time Auxiliary space When to use
Brute-force partitions O(n · 2^(n-1)) O(n) Small inputs or conceptual validation
Bottom-up DP O(n²) O(n) Default production implementation
Top-down cached DP O(n²) O(n) When expressing the recurrence directly is clearer

For the bottom-up implementation, there are n states and up to n line-ending choices per state, giving O(n²) time. The dp and breakpoint arrays require O(n) auxiliary space. The input is not counted; storing the formatted output requires space proportional to its character length. Best, average and worst-case times are identical. Top-down DP also uses O(n) space for its cache and recursion stack, but deep inputs may exceed Python’s default recursion limit.

Code Example

The main implementation is bottom-up and reconstructs the wrapped lines.

def word_wrap(words: list[str], width: int) -> tuple[int, list[str]]:
    """Return the minimum penalty and optimally wrapped lines."""
    if width <= 0:
        raise ValueError("width must be positive")
    if any(not word for word in words):
        raise ValueError("words must be non-empty")
    if any(len(word) > width for word in words):
        raise ValueError("a word exceeds the line width")
    if not words:
        return 0, []

    n = len(words)
    dp = [0] * (n + 1)
    next_break = [-1] * n

    # dp[start] stores the minimum cost for words[start:].
    for start in range(n - 1, -1, -1):
        line_length = 0
        best_cost = n * width * width + 1
        best_end = -1

        for end in range(start, n):
            line_length += len(words[end]) + (1 if end > start else 0)
            if line_length > width:
                break

            # The final line does not contribute to the penalty.
            line_cost = 0 if end == n - 1 else (width - line_length) ** 2
            candidate = line_cost + dp[end + 1]

            if candidate < best_cost:
                best_cost = candidate
                best_end = end

        dp[start] = best_cost
        next_break[start] = best_end

    # Reconstruct the selected line breaks.
    lines: list[str] = []
    start = 0
    while start < n:
        end = next_break[start]
        lines.append(" ".join(words[start:end + 1]))
        start = end + 1

    return dp[0], lines


penalty, lines = word_wrap(["a", "b", "c", "d"], 3)
print(penalty)  # 0
print(lines)    # ['a b', 'c d']

A top-down version using functools.cache directly expresses the recurrence:

from functools import cache


def word_wrap_top_down(words: list[str], width: int) -> int:
    """Return the minimum penalty using cached top-down DP."""
    if width <= 0:
        raise ValueError("width must be positive")
    if any(not word for word in words):
        raise ValueError("words must be non-empty")
    if any(len(word) > width for word in words):
        raise ValueError("a word exceeds the line width")
    if not words:
        return 0

    n = len(words)

    @cache
    def solve(start: int) -> int:
        if start == n:
            return 0

        line_length = 0
        best_cost = n * width * width + 1

        for end in range(start, n):
            line_length += len(words[end]) + (1 if end > start else 0)
            if line_length > width:
                break

            line_cost = 0 if end == n - 1 else (width - line_length) ** 2
            best_cost = min(best_cost, line_cost + solve(end + 1))

        return best_cost

    return solve(0)


print(word_wrap_top_down(["a", "b", "c", "d"], 3))  # 0

Edge Cases and Best Practices

  • Empty input: Returns penalty 0 and no lines.

  • One word: Produces one line if the word fits.

  • Duplicate words: Handled normally; duplicates are not removed.

  • Long or empty words: Raise ValueError because the function does not split or discard words.

  • Order: The input order is preserved. Sorting is irrelevant, and negative numbers, graphs, disconnected components and cycles do not apply to this problem.

  • If another objective is required, such as charging every line, change only line_cost; the DP structure remains the same.

  • The returned strings contain grouped words without padding. Actual justification can add trailing spaces to each non-final line.

Common Pitfalls

  • Forgetting to give the final line a cost of zero.

  • Using dp[j] instead of dp[j + 1] in the recurrence.

  • Failing to include one space between adjacent words when calculating line length.

  • Mutating or sorting the input when word order must remain fixed.

  • Using the recursive version for more than roughly 1,000 words without an explicit stack.

  • In fixed-width integer languages, choosing an overflow-safe “infinity” value for the initial cost.

28

How do you find the largest all-1 square in a binary matrix?

The maximal square problem asks for the largest square containing only 1s. Dynamic programming tracks the largest valid square ending at each cell, producing an optimal O(mn) time solution.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Let dp[i][j] represent the side length of the largest all-1 square whose bottom-right corner is cell (i, j).

  • Base cases: dp[0][j] = 0 and dp[i][0] = 0; any cell containing 0 also has value 0.

  • Recurrence: when matrix[i][j] == 1:

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Otherwise, dp[i][j] = 0. - Computation order: process rows from top to bottom and columns from left to right. - Final result: the maximum table value is the largest side length; its square is the requested area.

The rolling-row implementation keeps only the previous and current rows, reducing auxiliary space from O(mn) to O(n).

Why Dynamic Programming Applies

  • Overlapping subproblems: multiple cells reuse the same neighboring square results.

  • Optimal substructure: the best square ending at a cell depends only on the best squares ending at its upper, left, and upper-left neighbors.

Small Example

For this matrix:

Row Column 1 2 3
1 1 0 1
2 1 1 0
3 1 1 1

The filled DP table is:

Row Column 1 2 3
1 1 0 1
2 1 1 0
3 1 2 1
  1. The first two rows directly produce side lengths 1 and 0.

  2. At row 3, column 2, the recurrence gives min(1, 2, 1) + 1 = 2.

  3. The largest side length is 2, so the maximal square has area 2² = 4.

Complexity and Approach Choice

Let m be the number of rows and n the number of columns.

Approach Time Auxiliary space When to use
Brute-force square enumeration O(mn * min(m,n)^3) worst case (naive) O(1) Educational baseline only
Bottom-up DP O(mn) best, average, and worst O(n) Recommended production approach
Top-down memoized DP O(mn) best, average, and worst (assuming O(1) hash operations) O(mn) Small matrices or recursion depth is safe

Bottom-up DP visits every cell once. Top-down DP also has O(mn) memoization entries, and its recursion stack uses O(m+n) space. These space figures exclude the input matrix; counting the input makes total space O(mn).

Code Example

from functools import cache


def maximal_square_area(matrix: list[list[int]]) -> int:
    """Return the area of the largest square containing only ones."""
    if not matrix:
        return 0

    columns = len(matrix[0])
    if any(len(row) != columns for row in matrix):
        raise ValueError("Matrix rows must have equal lengths.")
    if columns == 0:
        return 0
    if any(value not in (0, 1) for row in matrix for value in row):
        raise ValueError("Matrix values must be 0 or 1.")

    previous = [0] * (columns + 1)
    largest_side = 0

    for row in matrix:
        current = [0] * (columns + 1)

        for column, value in enumerate(row, start=1):
            if value == 1:
                current[column] = 1 + min(
                    previous[column],
                    current[column - 1],
                    previous[column - 1],
                )

            largest_side = max(largest_side, current[column])

        previous = current

    return largest_side * largest_side


def maximal_square_area_top_down(matrix: list[list[int]]) -> int:
    """Return the maximal square area using memoized recursion."""
    if not matrix:
        return 0

    rows = len(matrix)
    columns = len(matrix[0])
    if any(len(row) != columns for row in matrix):
        raise ValueError("Matrix rows must have equal lengths.")
    if columns == 0:
        return 0
    if any(value not in (0, 1) for row in matrix for value in row):
        raise ValueError("Matrix values must be 0 or 1.")

    @cache
    def largest_side(row: int, column: int) -> int:
        if row < 0 or column < 0 or matrix[row][column] == 0:
            return 0

        return 1 + min(
            largest_side(row - 1, column),
            largest_side(row, column - 1),
            largest_side(row - 1, column - 1),
        )

    largest = max(
        largest_side(row, column)
        for row in range(rows)
        for column in range(columns)
    )
    return largest * largest


example_matrix = [
    [1, 0, 1],
    [1, 1, 0],
    [1, 1, 1],
]

print(maximal_square_area(example_matrix))              # 4
print(maximal_square_area_top_down(example_matrix))      # 4

Common Pitfalls and Interview Tips

  • Confirm whether the expected result is the side length or the area; this implementation returns area.

  • Initialize the extra row and column to zero to handle matrix boundaries consistently.

  • Do not mutate the input matrix.

  • Empty input, an empty first row, or a matrix without any 1s returns 0; a single 1 returns 1.

  • Negative or non-binary values and ragged rows are rejected explicitly.

  • The recursive version can reach depth O(m+n) and exceed Python’s default recursion limit of about 1000; use the iterative version for large matrices.

  • Common follow-ups include returning the square’s coordinates, counting all maximal squares, or finding the largest all-1 rectangle.

29

How to solve job scheduling for maximum profit using dynamic programming?

The maximum profit job scheduling problem finds the highest total profit from a set of jobs with start times, end times, and profits, without overlapping any two jobs. It is solved with dynamic programming by sorting jobs by end time and building a table of optimal subproblem answers.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Sort jobs by end time so that each job’s non-overlapping predecessor can be found with binary search.

  • State: dp[i] is the maximum profit achievable using the first i jobs (after sorting).

  • Recurrence: dp[i] = max(dp[i-1], profit_i + dp[p(i)]), where p(i) is the index of the last job that finishes before or at the start of job i.

  • Base case: dp[0] = 0 (no jobs).

  • Order: compute dp[i] for i = 1..n (bottom-up) or recurse from n with memoization (top-down).

  • The problem exhibits overlapping subproblems (many jobs share the same prefix) and optimal substructure (the optimal solution to a prefix includes the optimal solution to a smaller prefix).

  • Both top-down (recursion + functools.cache) and bottom-up (iterative table) work; the main code below uses the bottom-up approach.

Brute-Force vs Optimal

Approach Time Space When to use
Brute-force (all subsets) O(2^n) O(n) n ≤ 20
Dynamic programming O(n log n) O(n) All cases

Filled DP Table Example

Jobs sorted by end time: | i | Job (start, end, profit) | p(i) | dp[i] | |—|————————–|——|——-| | 0 | (none) | - | 0 | | 1 | (1, 2, 50) | 0 | 50 | | 2 | (3, 5, 20) | 1 | 70 | | 3 | (6, 8, 40) | 2 | 110 | | 4 | (2, 9, 60) | 1 | 110 |

Code Example

from bisect import bisect_right
from functools import cache
from typing import List, Tuple

def job_scheduling_max_profit(jobs: List[Tuple[int, int, int]]) -> int:
    """Return the maximum profit without overlapping jobs (bottom-up).

    Args:
        jobs: list of (start, end, profit) tuples.

    Example:
        >>> job_scheduling_max_profit([(1, 2, 50), (3, 5, 20), (6, 8, 40), (2, 9, 60)])
        110
    """
    if not jobs:
        return 0
    jobs = sorted(jobs, key=lambda x: x[1])
    n = len(jobs)
    end_times = [job[1] for job in jobs]
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        start, end, profit = jobs[i - 1]
        # find last job that finishes before this job starts
        p = bisect_right(end_times, start, 0, i - 1)
        dp[i] = max(dp[i - 1], profit + dp[p])
    return dp[n]

def job_scheduling_max_profit_top_down(jobs: List[Tuple[int, int, int]]) -> int:
    """Return the maximum profit without overlapping jobs (top-down with memoization)."""
    if not jobs:
        return 0
    jobs = sorted(jobs, key=lambda x: x[1])
    n = len(jobs)
    end_times = [job[1] for job in jobs]

    @cache
    def dfs(i: int) -> int:
        """Maximum profit using first i jobs (1-indexed)."""
        if i == 0:
            return 0
        start, end, profit = jobs[i - 1]
        p = bisect_right(end_times, start, 0, i - 1)
        return max(dfs(i - 1), profit + dfs(p))

    return dfs(n)

Complexity

  • Time (both approaches): O(n log n) — sorting takes O(n log n), and each of the n jobs uses binary search O(log n) to find its predecessor.

  • Space (bottom-up): O(n) for the dp table and end_times list. The input list is not counted as extra space. Space cannot be reduced below O(n) because predecessor lookups require random access.

  • Space (top-down): O(n) for the memoization cache and recursion stack (depth up to n). For large n, Python’s recursion limit may need to be increased or an explicit stack used.

Common Pitfalls

  • Forgetting to sort jobs by end time; the recurrence depends on this order.

  • Using bisect_left instead of bisect_right for finding the predecessor, which can include overlapping jobs.

  • Mutating the input list in place without copying, which can confuse interviewers.

  • Not handling the empty input case, which should return 0.

  • The formulation works for negative profits as well (it simply skips them), but typical problem statements assume non-negative profits.

  • One-element and duplicate jobs are handled correctly by the sort and binary search.

  • Interviewers often ask for the top-down recursive solution or for the actual set of jobs, not just the profit.

30

How does Floyd-Warshall use dynamic programming for shortest paths?

Dynamic programming enables Floyd-Warshall to compute all-pairs shortest paths by combining shorter subpaths through each possible intermediate vertex. The algorithm uses optimal substructure and reuses overlapping subproblems to avoid repeatedly solving the same path problems.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Let D[k][i][j] represent the shortest distance from vertex i to vertex j when only vertices 0 through k - 1 may be used as intermediate vertices, so D[0] allows none.

A shortest path either:

  • Does not pass through vertex k, retaining the previous distance.

  • Passes through vertex k, combining the shortest i → k and k → j distances.

The two properties that make dynamic programming applicable are:

  • Overlapping subproblems: The same subpath distances are reused across many larger path calculations.

  • Optimal substructure: An optimal path through k consists of optimal subpaths from i to k and from k to j.

Recurrence and Computation Order

The recurrence is:

D[k+1][i][j] = min(D[k][i][j], D[k][i][k] + D[k][k][j])

The base cases are:

  • D[0][i][j] is the direct edge weight, 0 when i == j, or infinity when no edge exists.

  • The diagonal starts at 0.

The bottom-up computation processes k from 0 to V-1, then every pair (i, j). Only the current distance matrix is needed, giving O(V²) space.

Small Example

For the directed graph:

0 → 1: 3
1 → 2: 4
2 → 0: 12
Stage Distance matrix
D[0] [0, 3, ∞]; [∞, 0, 4]; [12, ∞, 0]
D[1] (via 0) [0, 3, ∞]; [∞, 0, 4]; [12, 15, 0]
D[2] (via 0, 1) [0, 3, 7]; [∞, 0, 4]; [12, 15, 0]
D[3] (via 0, 1, 2) [0, 3, 7]; [16, 0, 4]; [12, 15, 0]

Allowing vertex 0 makes 2 → 1 equal 12 + 3 = 15. Allowing vertex 1 makes 0 → 2 equal 3 + 4 = 7. Allowing vertex 2 makes 1 → 0 equal 4 + 12 = 16.

Approach Trade-offs

Approach Time Space When to use
Brute-force path enumeration O(V!) worst case O(V²), including the matrix Tiny graphs only
Floyd-Warshall O(V³) O(V²) Dense graphs and all-pairs queries
Dijkstra from every vertex O(V(E + V) log V) O(E + V), plus O(V²) output Sparse graphs with nonnegative edges

For Floyd-Warshall, best, average and worst-case time are all O(V³): each of the V intermediate vertices requires checking V² vertex pairs. Space is O(V²), excluding the input matrix, because only one matrix is retained. Including the input, total space remains O(V²).

Code Example

The main implementation uses bottom-up tabulation. The top-down version defines the state shortest(k, i, j) and memoizes it with functools.cache.

from functools import cache
from math import inf

Matrix = list[list[float]]


def _prepare_matrix(weights: Matrix) -> Matrix:
    size = len(weights)
    if any(len(row) != size for row in weights):
        raise ValueError("The weight matrix must be square")

    distance = [[float(value) for value in row] for row in weights]
    for vertex in range(size):
        distance[vertex][vertex] = 0.0
    return distance


def floyd_warshall(weights: Matrix) -> Matrix:
    """Return all-pairs shortest paths using bottom-up tabulation."""
    distance = _prepare_matrix(weights)
    size = len(distance)

    for k in range(size):
        for i in range(size):
            for j in range(size):
                through_k = distance[i][k] + distance[k][j]
                distance[i][j] = min(distance[i][j], through_k)

    return distance


def floyd_warshall_top_down(weights: Matrix) -> Matrix:
    """Return all-pairs shortest paths using memoized recursion."""
    distance = _prepare_matrix(weights)
    size = len(distance)

    @cache
    def shortest(k: int, i: int, j: int) -> float:
        # Vertices 0 .. k-1 may be intermediates; k == 0 means direct edges.
        if k == 0:
            return distance[i][j]

        without_k = shortest(k - 1, i, j)
        through_k = shortest(k - 1, i, k - 1) + shortest(k - 1, k - 1, j)
        return min(without_k, through_k)

    return [
        [shortest(size, i, j) for j in range(size)]
        for i in range(size)
    ]


weights: Matrix = [
    [0.0, 3.0, inf],
    [inf, 0.0, 4.0],
    [12.0, inf, 0.0],
]

print(floyd_warshall(weights))
# [[0.0, 3.0, 7.0], [16.0, 0.0, 4.0], [12.0, 15.0, 0.0]]

print(floyd_warshall_top_down(weights))
# [[0.0, 3.0, 7.0], [16.0, 0.0, 4.0], [12.0, 15.0, 0.0]]

Common Pitfalls

  • Infinite distances: Disconnected vertices remain unreachable; infinity plus infinity is still infinity.

  • Negative cycles: Floyd-Warshall can use negative edges only if the graph has no negative-weight cycle. Negative cycles require separate detection.

  • Input mutation: These implementations copy the matrix, so callers’ inputs remain unchanged.

  • Recursion depth: The top-down implementation uses O(V) recursion depth and may exceed Python’s default recursion limit for large graphs. Its cache uses O(V³) space, including cached states, so bottom-up is normally preferable.

  • Edge cases: Empty input returns []; a one-vertex graph returns [[0.0]].

  • Common follow-up: Explain why the recurrence considers exactly two cases, or adapt the algorithm to retrieve an actual shortest path by storing predecessor information.

31

How to use dynamic programming to count paths in a DAG?

You use dynamic programming to count paths by summing the ways to reach each vertex’s predecessors in topological order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • State: dp[v] is the number of distinct paths from the source vertex to vertex v.

  • Recurrence: dp[v] = sum(dp[u] for u in predecessors(v)).

  • Base case: dp[source] = 1.

  • Order: Process vertices in topological order so that all predecessors are resolved before a vertex.

Overlapping Subproblems and Optimal Substructure

  • Overlapping subproblems: The same vertex is reached via multiple paths, so its count is computed once and reused.

  • Optimal substructure: The number of paths to v is the sum of the optimal counts of its predecessors.

Top-Down vs Bottom-Up

Approach Time Space When to use
Top-down (memoization) O(V + E) O(V) + recursion stack When the graph is sparse or you want to avoid full topological sort
Bottom-up (iterative) O(V + E) O(V) Standard for DAGs; avoids recursion depth limits

Step-by-Step Example

Consider a DAG with edges 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3. Source is 0, target is 3.

  1. Topological order: 0, 1, 2, 3.

  2. Initialize dp array: [1, 0, 0, 0].

  3. Process 0: no predecessors, dp[0] = 1.

  4. Process 1: predecessor 0, dp[1] = dp[0] = 1.

  5. Process 2: predecessor 0, dp[2] = dp[0] = 1.

  6. Process 3: predecessors 1 and 2, dp[3] = dp[1] + dp[2] = 2.

The filled DP table is [1, 1, 1, 2], so there are 2 paths to vertex 3.

Code Example

Bottom-up (main implementation)

from collections import deque

def count_paths_bottom_up(graph: list[list[int]], source: int, target: int) -> int:
    """Count distinct paths from source to target in a DAG using bottom-up DP.

    Args:
        graph: Adjacency list where graph[v] contains vertices reachable from v.
        source: Starting vertex index.
        target: Destination vertex index.

    Returns:
        Number of distinct paths from source to target.
    """
    n = len(graph)
    in_degree = [0] * n
    for v in range(n):
        for neighbor in graph[v]:
            in_degree[neighbor] += 1

    # Kahn's algorithm for topological order
    queue = deque([v for v in range(n) if in_degree[v] == 0])
    order = []
    while queue:
        v = queue.popleft()
        order.append(v)
        for neighbor in graph[v]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # DP over topological order
    dp = [0] * n
    dp[source] = 1
    for v in order:
        for neighbor in graph[v]:
            dp[neighbor] += dp[v]

    return dp[target]

# Example: graph = [[1, 2], [3], [3], []], source = 0, target = 3
# Output: 2

Top-down (memoization with functools.cache)

from functools import cache

def count_paths_top_down(graph: list[list[int]], source: int, target: int) -> int:
    """Count distinct paths from source to target in a DAG using top-down DP.

    Note: Recursion depth may exceed Python's limit for very deep graphs.
    """
    # Build reverse adjacency list (predecessors) for the recurrence
    n = len(graph)
    pred = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            pred[v].append(u)

    @cache
    def dp(v: int) -> int:
        if v == source:
            return 1
        return sum(dp(u) for u in pred[v])

    return dp(target)

# Example: graph = [[1, 2], [3], [3], []], source = 0, target = 3
# Output: 2

The bottom-up approach runs in O(V + E) time because each vertex and edge is processed once, and uses O(V) space for the DP array and topological order. The top-down approach has the same asymptotic complexity but uses the recursion stack.

Common Pitfalls

  • Assuming cycles: The algorithm requires a DAG; a cycle breaks topological ordering.

  • Off-by-one errors: Ensure the source vertex is initialized to 1, not 0.

  • Mutating input: Do not modify the graph while computing in-degrees.

  • Ignoring unreachable vertices: The DP returns 0 for vertices not reachable from the source.

  • Recursion depth: Top-down memoization can exceed Python’s recursion limit for deep graphs.

32

How do you solve the Nim Game using Dynamic Programming?

A dynamic-programming solution represents each Nim position as a tuple of heap sizes and determines whether the current player can force a win. This is correct, although the classic XOR theorem solves standard Nim more efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

DP State and Recurrence

Let dp[heaps] indicate whether the player whose turn it is can force a win from the position heaps.

  • State: heaps is a tuple containing the current size of every heap.

  • Base case: dp[(0, ..., 0)] = False; with no stones, the current player loses.

  • Recurrence: A non-empty position is winning if at least one legal move reduces one heap and leaves the opponent in a losing position.

  • Computation order:

  • Top-down: evaluate successors recursively and memoize results with functools.cache.

  • Bottom-up: process positions in decreasing order of total stones, ensuring every successor is already known.

The DP exhibits overlapping subproblems because different move sequences can reach the same heap configuration. It has optimal substructure because the current position’s outcome depends on the outcomes of its legal successor positions.

Approach Comparison

Let k be the number of heaps, S their total stones, H the largest heap, and P = ∏(hᵢ + 1) the number of bounded configurations.

Approach Time Auxiliary space When to use
Brute-force recursion O(k^S) O(S) Very small examples only
Memoized DP O(Pk²H) worst case O(Pk + S) Teaching overlapping subproblems
Bottom-up DP table O(P log P + Pk²H) worst case O(Pk) Moderate heap sizes
XOR theorem O(k) O(1) Standard Nim in practice

The k² factor includes the cost of creating and hashing length-k tuple states. Best, average, and worst-case bounds do not differ asymptotically because the work is determined by the heap bounds rather than their order.

Filled Example Table

For heaps (2, 1), the complete bounded DP table is:

Position Player to move
(2, 1) Winning
(2, 0) Winning
(1, 1) Losing
(1, 0) Winning
(0, 1) Winning
(0, 0) Losing

For example, (2, 1) is winning because reducing the first heap to 1 leaves (1, 1), which is losing.

Code Example

The main implementation uses bottom-up DP and also returns a winning move. The top-down implementation demonstrates memoization.

from functools import cache
from itertools import product


def can_win_top_down(heaps: tuple[int, ...]) -> bool:
    """Return whether the current player can force a win in Nim."""
    if any(size < 0 for size in heaps):
        raise ValueError("Heap sizes cannot be negative")

    @cache
    def win(state: tuple[int, ...]) -> bool:
        if not any(state):
            return False

        for index, size in enumerate(state):
            for remaining in range(size):
                next_state = (
                    state[:index] + (remaining,) + state[index + 1:]
                )
                if not win(next_state):
                    return True

        return False

    return win(heaps)


def solve_nim_dp(
    heaps: tuple[int, ...],
) -> tuple[bool, tuple[int, int] | None]:
    """Return the winner and a winning move using bottom-up Nim DP."""
    if any(size < 0 for size in heaps):
        raise ValueError("Heap sizes cannot be negative")

    if not heaps:
        return False, None

    states = sorted(
        product(*(range(size + 1) for size in heaps)),
        key=sum,
        reverse=True,
    )
    winning: dict[tuple[int, ...], bool] = {}

    for state in states:
        if not any(state):
            winning[state] = False
            continue

        state_wins = False
        for index, size in enumerate(state):
            for remaining in range(size):
                next_state = (
                    state[:index] + (remaining,) + state[index + 1:]
                )
                if not winning[next_state]:
                    state_wins = True
                    break
            if state_wins:
                break

        winning[state] = state_wins

    for index, size in enumerate(heaps):
        for remaining in range(size):
            next_state = (
                heaps[:index] + (remaining,) + heaps[index + 1:]
            )
            if not winning[next_state]:
                return True, (index, remaining)

    return False, None


print(can_win_top_down((2, 1)))   # True
print(solve_nim_dp((2, 1)))        # (True, (0, 1))

Common Pitfalls and Interview Tips

  • Empty input: Treat zero heaps as a losing position.

  • Single heap: Any positive heap is winning by reducing it to zero.

  • Duplicate heaps: Treat them as separate heaps; duplicates are valid Nim positions.

  • Negative sizes: Reject them explicitly.

  • Recursion depth: The top-down version can recurse about S levels, so it may exceed Python’s default limit near 1000. Use the bottom-up version for larger totals or raise the limit deliberately.

  • Move ordering: Heap order does not affect the result.

  • Cycles: Impossible in Nim because every move strictly decreases the total number of stones.

  • Practical follow-up: Interviewers often ask why standard Nim is solved by XOR; the result is winning exactly when the XOR of all heap sizes is nonzero.

33

How to solve minimax games using dynamic programming

Dynamic programming solves minimax games by caching the best value of each reachable state instead of repeatedly evaluating the same positions. The implementation below applies this general principle to the classic game in which players alternately take the leftmost or rightmost number.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

For a general finite two-player game, let V(s) be the score difference Player 1 can guarantee from state s.

  • Recurrence: On Player 1’s turn, take the maximum value among successor states; on Player 2’s turn, take the minimum. A terminal state has a fixed payoff, commonly 1, 0, or -1 for a win, draw, or loss.

  • Overlapping subproblems: Different move sequences can reach the same state, so its value should be computed only once.

  • Optimal substructure: The value of a state depends only on the optimal values of its successor states.

  • Order: Use memoized recursion, or process states from terminals backward in a topological order when the state graph is acyclic.

For the concrete endpoint game, define dp[i][j] as the maximum final score difference, measured as the player to move minus the opponent, obtainable from nums[i..j].

  • Recurrence: dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]). The subtraction changes the perspective to the opponent.

  • Base case: dp[i][i] = nums[i].

  • Order: Compute intervals in increasing length.

Complexity and Optimization

All space figures below are auxiliary space and exclude the O(n) input. Including the input does not change these asymptotic bounds.

Approach Time Space When to use
Brute-force recursion O(2^n) for all move sequences O(n) recursion stack Very small inputs
Bottom-up DP O(n²) for O(n²) states O(n²) table Standard interview solution
Space-optimized DP O(n²) for O(n²) states O(n) array When table memory matters

The top-down solution uses O(n²) memoization space plus an O(n) recursion stack, so its total auxiliary space remains O(n²).

For O(n) space, initialize values[i] = nums[i], then iterate i from right to left and j from i + 1 rightward. Update values[j] using the old values[j] and the already updated values[j-1]. For a generic acyclic game with S states and at most b moves per state, memoized minimax takes O(Sb) time and O(S) cache space, plus up to O(S) recursion stack space.

Example Walkthrough

For nums = [1, 5, 2]:

i j 0 1 2
0 1 4 -2
1 — 5 3
2 — — 2
  1. Length-one intervals have values 1, 5, and 2.

  2. Length-two intervals have values max(1-5, 5-1) = 4 and max(5-2, 2-5) = 3.

  3. The full interval has value max(1-3, 2-4) = -2, so the first player finishes two points behind.

Code Example

The main implementation uses the bottom-up table approach to avoid recursion-depth limits.

def max_score_difference(nums: list[int]) -> int:
    """Return the optimal score difference for the player to move."""
    if not nums:
        return 0

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

    for i, value in enumerate(nums):
        dp[i][i] = value

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(
                nums[i] - dp[i + 1][j],
                nums[j] - dp[i][j - 1],
            )

    return dp[0][n - 1]


print(max_score_difference([1, 5, 2]))  # -2

The equivalent top-down implementation uses recursion with functools.cache:

from functools import cache


def max_score_difference_top_down(nums: list[int]) -> int:
    """Return the optimal score difference for the player to move."""
    if not nums:
        return 0

    @cache
    def dp(i: int, j: int) -> int:
        if i == j:
            return nums[i]
        return max(
            nums[i] - dp(i + 1, j),
            nums[j] - dp(i, j - 1),
        )

    return dp(0, len(nums) - 1)


print(max_score_difference_top_down([1, 5, 2]))  # -2

Common Pitfalls

  • Sign flip: Subtract the opponent’s value because it is measured from the opponent’s perspective.

  • Off-by-one errors: Check interval bounds and handle one-element intervals explicitly.

  • Recursion depth: The top-down recursion can approach Python’s default recursion limit for large inputs.

  • Edge cases: Empty input returns 0; one element returns that element. Duplicates, negative numbers, and already sorted input require no special handling. Graph-specific cases such as disconnected graphs and cycles do not occur in this interval game; generic cyclic games require explicit cycle handling.

  • Input mutation: Do not modify nums; both implementations only read it.

  • Win versus tie: The first player wins only when the final difference is > 0; 0 means a tie.

34

Can dynamic programming solve probabilistic state problems

Yes, dynamic programming can solve problems with probabilistic states. When transitions between states follow probability distributions rather than deterministic rules, the recurrence computes expected values or probabilities by summing over all possible next states weighted by their transition probabilities. This approach is commonly called probabilistic DP or expected-value DP.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

In standard DP, each state has a deterministic set of next states. In probabilistic DP, each state transitions to other states with given probabilities. The recurrence takes the form:

dp[i] = sum over j of P(i -> j) * dp[j] + cost(i)

where P(i -> j) is the probability of transitioning from state i to state j, and cost(i) is the immediate cost of being in state i. The key insight is that the expected value of the future is the probability-weighted average of the expected values of all possible futures.

Required Properties

Probabilistic DP still requires the two properties that make DP work:

  • Overlapping subproblems: The same states are reached repeatedly through different paths, so memoization or a table avoids recomputation.

  • Optimal substructure: The optimal solution to a problem contains optimal solutions to subproblems. For probabilistic DP, this means the expected value from a state depends only on the expected values of the states it can reach.

Example Walkthrough

Consider a random walk where you start at position n and want to reach position 0. At each step, you move left toward 0 with probability p, or stay in place with probability 1 - p.

  • State: dp[i] = expected number of steps to reach 0 from position i.

  • Base case: dp[0] = 0 (already at the target).

  • Recurrence: dp[i] = 1 + p * dp[i-1] + (1-p) * dp[i]. The 1 counts the current step.

Rearranging: p * dp[i] = 1 + p * dp[i-1], so dp[i] = dp[i-1] + 1/p. Each step back adds 1/p to the expected count.

i dp[i] (p=0.5)
0 0
1 2
2 4
3 6

Complexity

  • Time: O(n) — one pass through the states, each computed in O(1).

  • Space: O(n) for the DP table. This can be reduced to O(1) by keeping only the previous value, since dp[i] depends only on dp[i-1].

Common Pitfalls

  • Circular dependencies: Some probabilistic DP formulations (like consecutive heads) create equations where a state references itself. These require solving a system of linear equations, not a simple loop.

  • Forgetting base cases: Absorbing states (like reaching 0) must be initialized correctly, or the recurrence propagates wrong values.

  • Probability normalization: Ensure all transition probabilities from a state sum to 1. Missing probability mass breaks the expected-value calculation.

  • Follow-up: Interviewers often ask how to handle states with multiple probabilistic transitions, or how to compute the probability of reaching a specific state rather than the expected value.

35

What are the differences and applications of stochastic dynamic programming?

Stochastic dynamic programming optimizes decisions when future outcomes follow probability distributions, whereas deterministic dynamic programming assumes each action produces a known outcome. Stochastic DP typically maximizes expected reward or minimizes expected cost rather than optimizing a guaranteed outcome.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Aspect Deterministic DP Stochastic DP
Future outcome Known exactly Uncertain, with a probability distribution
Objective Optimize deterministic reward or cost Optimize expected reward or cost
Transition model next_state = f(state, action) A probability distribution over next states
Bellman equation Uses one successor value Uses an expectation across possible successors
Main modeling challenge Representing dependencies Representing uncertainty and required state information
Typical example Select a machine with known processing time Set inventory levels when demand is uncertain

A stochastic policy can still select a deterministic action for each state. Randomness usually comes from the environment—for example, uncertain demand, arrival times, weather, or equipment failures.

DP Model and Computation

Define the DP elements as follows:

  • State s: all information required to make the next decision.

  • Action a: a decision available in state s.

  • Reward R(s, a, S'): immediate payoff, possibly depending on the random next state S'.

  • Value V_t(s): optimal expected cumulative reward from state s with exactly t decisions remaining.

For a finite horizon, the stochastic Bellman recurrence is:

[ V_t(s)=max_{a in A(s)} Eleft[R(s,a,S’)+gamma V_{t-1}(S’)mid s,aright] ]

The base case is V_0(s) = g(s), where g(s) is any specified terminal payoff; often g(s) = 0. Compute layers in increasing order from t = 1 through T, equivalently backward through calendar time, because each layer depends on the layer with one fewer decision remaining.

The deterministic recurrence is:

[ V_t(s)=max_{a in A(s)} left[r(s,a)+gamma V_{t-1}(f(s,a))right] ]

Both rely on:

  • Overlapping subproblems: different histories or decisions can reach the same state and reuse its value.

  • Optimal substructure: an optimal policy uses an optimal action now and optimal continuation decisions afterward.

For an infinite-horizon discounted problem, the recurrence becomes a Bellman fixed-point equation, commonly solved using value iteration or policy iteration.

Worked Example

Suppose one decision remains at s0. The action produces:

  • Immediate reward 10 and transition to s1 with probability 0.4.

  • Immediate reward 0 and transition to terminal state s2 with probability 0.6.

No decisions remain afterward and there is no additional terminal payoff. Therefore, V_0(s1) = V_0(s2) = 0.

The filled value table is:

State V_0(s) V_1(s)
s0 0 4
s1 0 0
s2 0 0

The calculation is:

[ V_1(s0)=0.4(10+0)+0.6(0+0)=4 ]

Thus, the expected value is 4, even though one possible realized reward is 10.

Applications

  • Inventory management: Set reorder levels when customer demand is uncertain.

  • Queueing and resource allocation: Assign servers or staff when arrival rates vary.

  • Scheduling: Plan work when task durations or equipment availability are uncertain.

  • Routing: Select routes under uncertain travel times or disruptions.

  • Finance and portfolio optimization: Choose allocations under uncertain returns.

  • Healthcare: Optimize treatment policies under uncertain disease progression.

  • Energy systems: Manage storage and generation under uncertain demand or renewable output.

  • Reinforcement learning: Model and solve Markov decision processes with stochastic transitions.

Complexity

For a finite tabular model with n states, at most m actions per state, and at most k_max outcomes per state-action pair, one complete Bellman optimality backup costs:

  • Deterministic model: O(nm) time in the best, average, and worst cases.

  • Stochastic model: O(nm) best time when each pair has one outcome, O(nm × k̄) average time, and O(nm × k_max) worst time, where k̄ is the mean number of outcomes per pair.

Space bounds:

  • Stored transition model: O(nm × k_max + n + m) total space, counting the model and action sets as input.

  • Auxiliary space excluding that input: O(n + m) for values and a deterministic policy.

  • Finite-horizon values: storing every layer requires O(nT) auxiliary space; retaining only the current and next layers reduces it to O(n).

  • Recursion stack: iterative backward induction uses no recursion stack. Recursive top-down evaluation adds up to O(T) stack frames, which must be counted in auxiliary space.

For continuous states, unbounded actions, or simulated transitions, complexity depends on the approximation method and number of model evaluations.

Common Pitfalls

  • Maximizing the best possible outcome instead of the expected objective.

  • Ignoring risk or variance when the objective is not purely expectation-based.

  • Omitting history-dependent information required for the Markov assumption.

  • Using a deterministic successor equation when multiple outcomes are possible.

  • Forgetting the terminal condition or computing Bellman layers in the wrong order.

  • Assuming an expected reward guarantees that outcome will occur.

  • Using naive recursive evaluation for a cyclic model; use iterative fixed-point computation with a convergence criterion.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 35 Dynamic Programming answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects