Context

At a logistics company operating in 50+ cities with millions of daily deliveries, small algorithmic improvements can save significant fuel and driver time. Many optimization tasks (route pricing, batching, capacity planning) involve exploring many combinations, where a naive recursive solution can explode exponentially and miss latency SLOs.

Core Question

1. Explain dynamic programming (DP) in your own words. What problem characteristics make DP applicable?
2. Define and contrast overlapping subproblems and optimal substructure. Why are both important?
3. Give a concrete example (you choose) and do the following:
   • Write the state definition (what does dp[i] or dp[i][j] mean?).
   • Provide the recurrence relation and base cases.
   • Explain whether you would implement it as top-down (memoization) or bottom-up (tabulation) and why.
   • State the time and space complexity.
4. Discuss common pitfalls: incorrect state choice, missing base cases, double-counting, and when DP is the wrong tool.

Scope Guidance

Aim for an interview-level explanation: clear definitions, a worked example with a recurrence, and trade-offs between memoization vs tabulation. You don’t need to prove correctness formally, but you should be able to justify why your recurrence covers all cases and avoids recomputation.

Overlapping Subproblems

A problem has overlapping subproblems when the same smaller inputs are solved repeatedly in a naive recursive approach. DP improves performance by caching these results so each subproblem is computed once (or a small constant number of times).

from functools import lru_cache

@lru_cache(None)
def f(i: int) -> int:
    # f(i) will be computed once per i
    ...

Optimal Substructure

A problem has optimal substructure when an optimal solution can be constructed from optimal solutions to its subproblems. This property is what makes a recurrence valid: choosing the best among subproblem-based candidates yields a globally optimal answer.

State and Transition (Recurrence)

The DP state is the minimal information needed to describe a subproblem (e.g., position, remaining capacity, last choice). The transition describes how to compute the state from smaller states, turning an exponential search into a polynomial-time computation.

# Example shape:
# dp[i] = min cost to reach i
# dp[i] = min(dp[i-1] + cost1, dp[i-2] + cost2)

Top-Down vs Bottom-Up

Top-down DP (memoization) starts from the original problem and recursively computes only needed subproblems, caching results. Bottom-up DP (tabulation) iterates in an order that guarantees dependencies are already computed; it often makes space optimizations easier and avoids recursion depth limits.

# Bottom-up skeleton
for i in range(1, n+1):
    dp[i] = ... # uses dp[i-1], dp[i-2], ...

Space Optimization

Many DP recurrences only depend on a fixed window of previous states (e.g., last 2 values). In those cases, you can reduce space from O(n) to O(1) by keeping only the necessary rolling variables.

prev2, prev1 = 0, 1
for _ in range(2, n+1):
    prev2, prev1 = prev1, prev1 + prev2