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.