1-D Dynamic Programming
Breaking a problem into overlapping subproblems indexed by a single variable, solved once each and reused.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain overlapping subproblems using naive recursive Fibonacci as an example, and how memoization fixes it.(show answer)
Naive recursive fib(n) = fib(n-1) + fib(n-2) recomputes the same subproblems repeatedly — e.g. fib(5) calls fib(3) twice, fib(2) three times, and so on, causing this exponential O(2^n) blowup. Memoization stores each subproblem's result the first time it's computed (in a cache keyed by input), so subsequent calls with the same input return instantly instead of recomputing — reducing it to O(n), since each distinct subproblem is now solved only once.
Q2.What is "optimal substructure," and why is it required for DP to apply?(show answer)
A problem has optimal substructure if its optimal solution can be constructed from optimal solutions to its subproblems — e.g. the shortest path from A to C through B is the shortest A-to-B path plus the shortest B-to-C path. Without this property, solving subproblems optimally wouldn't help solve the larger problem optimally, so there'd be no way to build up an answer from cached subproblem results — DP fundamentally relies on this compositional structure.
Q3.How would you solve the "climbing stairs" problem (n steps, can move 1 or 2 steps at a time, count distinct ways to reach the top) with bottom-up DP?(show answer)
Define dp[i] = number of ways to reach step i. Base cases: dp[0] = 1, dp[1] = 1. For each subsequent step, dp[i] = dp[i-1] + dp[i-2] — the number of ways to reach step i is the sum of ways to reach it from one step back or two steps back. Iterate from 2 up to n, filling the array bottom-up; the answer is dp[n]. This runs in O(n) time and, since only the last two values are needed at each step, can be optimized to O(1) space.
Q4.When would you prefer top-down (memoized recursion) over bottom-up (tabulation), or vice versa?(show answer)
Top-down is often more natural to write — it mirrors the recursive problem definition directly, and it automatically only computes subproblems that are actually needed for the specific input, which can save work if not every subproblem in the full table is reachable. Bottom-up avoids recursion's call-stack overhead and risk of stack overflow on deep recursion, and makes it more straightforward to apply space optimizations (like keeping only the last few computed values instead of the whole table).