# Dynamic Programming Intuition

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/dynamic-programming-intuition

## What is Dynamic Programming?

**Dynamic programming (DP)** solves problems with **overlapping subproblems**—where the exact same smaller problem is needed many times. Instead of recomputing answers, you **solve each subproblem once and store its answer**.

Take the naive recursive **Fibonacci** formula $F(n) = F(n-1) + F(n-2)$. Plain recursion recalculates $F(3)$ twice and $F(2)$ three times, causing **exponential explosion**. Because there are only $n$ distinct subproblems, storing them collapses the cost to $O(n)$ time.

| Style | Direction | How It Works |
| --- | --- | --- |
| **Memoization** | Top-down | Natural recursion that caches results on the first call |
| **Tabulation** | Bottom-up | Fills a table from smallest to largest subproblem |

DP requires two core features: **overlapping subproblems** and **optimal substructure**, where an optimal solution builds directly on optimal subproblem solutions.

## DP vs. Divide-and-Conquer

Students often confuse dynamic programming with **divide-and-conquer**. The distinction rests entirely on whether subproblems share work.

| Feature | Divide-and-Conquer | Dynamic Programming |
| --- | --- | --- |
| **Subproblems** | **Independent** (e.g., merge sort halves) | **Overlapping** (reused constantly) |
| **Core Goal** | Divide and combine | **Store and reuse** results |

**Common pitfall:** Applying divide-and-conquer logic to a problem with overlapping subproblems, which triggers catastrophic redundant work. 

Classic DP applications include shortest paths, edit distance, the knapsack problem, and longest common subsequence. Each turns an intractable exponential brute-force search into an efficient polynomial-time solution simply by remembering past subresults.

## Practice questions

5 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Match each dynamic programming concept to its meaning.

**Answer:**

- Memoization → Top-down recursion that caches each result
- Tabulation → Bottom-up filling of a table of subproblem answers
- Overlapping subproblems → The same subproblem is needed many times
- Optimal substructure → An optimal solution built from optimal subsolutions

**Why:** Memoization and tabulation are the two DP styles (top-down caching versus bottom-up table filling); overlapping subproblems and optimal substructure are the two properties that make DP applicable.

Page: https://tryals.app/practice/computer-science-i/dynamic-programming-intuition/match-each-dynamic-programming-concept-to-its-meaning

### 2. Memoisation and tabulation both solve the same dynamic programming problems. When does the choice actually matter?

A. When the problem has overlapping subproblems, which only memoisation handles
B. When only part of the state space is ever reached
C. Never, the two are interchangeable in every respect
D. When the recursion is too deep, which tabulation cannot express

**Answer:** B. When only part of the state space is ever reached

**Why:** Tabulation fills everything; memoisation computes only what the recursion reaches. On a sparse state space that is the whole difference, and it runs the other way too, since tabulation avoids call overhead and stack depth. Neither dominates, which is why both are taught.

Page: https://tryals.app/practice/computer-science-i/dynamic-programming-intuition/memoisation-and-tabulation-both-solve-the-same-dynamic-programming

### 3. Select every problem the lesson names as a classic dynamic programming problem.

A. Longest common subsequence
B. Edit distance
C. Shortest paths
D. Merge sort
E. Knapsack

**Answer:** A. Longest common subsequence; B. Edit distance; C. Shortest paths; E. Knapsack

**Why:** Shortest paths, edit distance, knapsack, and longest common subsequence are the named DP problems. Merge sort is divide-and-conquer, its halves are independent, so there is nothing to reuse.

Page: https://tryals.app/practice/computer-science-i/dynamic-programming-intuition/select-every-problem-the-lesson-names-as-a-classic-dynamic

### 4. Sort each description by which style of dynamic programming it belongs to.

**Answer:**

- Memoization (top-down): Write the natural recursion and cache results as computed, Return a stored value on later calls
- Tabulation (bottom-up): Fill a table from the smallest subproblem upward, Ensure each entry is ready before larger ones need it

**Why:** Memoization keeps the natural recursion but caches; tabulation abandons recursion and fills a table from the base cases up. Both compute the same answers, just in opposite directions.

Page: https://tryals.app/practice/computer-science-i/dynamic-programming-intuition/sort-each-description-by-which-style-of-dynamic-programming-it

### 5. Naive recursive Fibonacci takes exponential time; adding memoisation makes it linear. Why does storing results change the growth class so dramatically?

A. Because storing results allows the compiler to optimise the recursion away.
B. Because the naive version recomputes the same subproblems exponentially.
C. Because memoisation makes each individual addition faster.
D. Because the memoised version uses a loop internally rather than recursion.

**Answer:** B. Because the naive version recomputes the same subproblems exponentially.

**Why:** Draw the call tree and the waste is visible: about 2ⁿ nodes containing only n distinct values. Memoisation removes duplication rather than speeding anything up, so the work becomes proportional to the number of distinct subproblems. That identifies when the technique applies, overlapping subproblems, plus optimal substructure. Merge sort's halves are all distinct, so there is nothing to reuse.

Page: https://tryals.app/practice/computer-science-i/dynamic-programming-intuition/naive-recursive-fibonacci-takes-exponential-time-adding-memoisation