Dynamic Programming

Recurrence Relations, Memoization, and Optimal Substructure — A TLDR Primer

Dynamic programming shows up on AP Computer Science exams, college algorithms midterms, and nearly every technical coding interview — and it trips up students at every level. The core idea sounds simple: break a big problem into smaller ones and reuse the answers instead of recalculating them. But translating that idea into a working solution, with the right state, the right recurrence, and the right base case, is where most students get stuck.

This TLDR guide is a focused introduction to dynamic programming for high school and early college students who need to get oriented fast. Short by design, you'll build from the ground up: starting with Fibonacci to make the idea concrete, then moving through a reusable four-step DP recipe, then applying it to the problems that actually appear on exams and in interviews — coin change, longest increasing subsequence, grid path counting, 0/1 knapsack, and longest common subsequence.

Every section leads with the one thing you need to take away, works through numbered examples with real tables and recurrences, and calls out the misconceptions that cause students to lose points. The final section contrasts dynamic programming with greedy algorithms and gives you concrete heuristics for spotting a dp problem on sight — including the patterns that separate DP from every other algorithmic approach.

If you're prepping for an algorithms course, a technical interview, or just need a clean intro to dp recurrence relations and problem-solving patterns, this guide gets you there without the filler.

Pick it up and work through it in an afternoon.

What you'll learn

Recognize when a problem has optimal substructure and overlapping subproblems
Convert a recursive solution into a memoized solution and then into a bottom-up table
Define a DP state, recurrence, and base case for classic problems like Fibonacci, climbing stairs, coin change, and longest common subsequence
Analyze the time and space complexity of a DP solution and apply space optimization
Distinguish DP from greedy algorithms and plain recursion, and avoid common pitfalls

What's inside

1. What Dynamic Programming Actually Is

Introduces DP as the technique of solving big problems by reusing answers to smaller overlapping subproblems, motivated by the Fibonacci example.
2. The DP Recipe: State, Recurrence, Base Case

Lays out the four-step process for designing any DP solution and walks through climbing stairs and house robber as worked examples.
3. 1D Problems: Coin Change and Longest Increasing Subsequence

Tackles two canonical 1D DP problems where the state is a single index or amount, emphasizing how to set up the recurrence when multiple choices feed into one state.
4. 2D Problems: Grids, Knapsack, and LCS

Extends DP to two-dimensional tables using grid path counting, the 0/1 knapsack problem, and longest common subsequence.
5. DP vs Greedy, and How to Spot DP on an Exam

Contrasts dynamic programming with greedy algorithms and gives concrete heuristics for recognizing DP problems and avoiding common traps.

Published by Solid State Press

TLDR STUDY GUIDES

Dynamic Programming

Recurrence Relations, Memoization, and Optimal Substructure — A TLDR Primer

Solid State Press

Dynamic Programming

Recurrence Relations, Memoization, and Optimal Substructure — A TLDR Primer

Published by Solid State Press.

Part of the TLDR Study Guides series.

1 What Dynamic Programming Actually Is
2 The DP Recipe: State, Recurrence, Base Case
3 1D Problems: Coin Change and Longest Increasing Subsequence
4 2D Problems: Grids, Knapsack, and LCS
5 DP vs Greedy, and How to Spot DP on an Exam

Chapter 1

What Dynamic Programming Actually Is

Suppose you need to compute the 50th Fibonacci number. The Fibonacci sequence is defined simply: each number is the sum of the two before it, starting with $F(1) = 1$ and $F(2) = 1$. So $F(3) = 2$, $F(4) = 3$, $F(5) = 5$, and so on. The recursive definition almost writes its own code:

fib(n):
    if n <= 2: return 1
    return fib(n-1) + fib(n-2)

Clean. Readable. Also catastrophically slow. To compute fib(50), your computer calls fib(49) and fib(48). To compute fib(49), it calls fib(48) and fib(47). Notice that fib(48) is now being computed twice. By the time you reach fib(5), it will have been recomputed millions of times. The total number of calls grows exponentially — roughly $2^n$ — which means fib(50) triggers about a trillion function calls.

This is the problem that dynamic programming (DP) solves. DP is a technique for speeding up computations by storing the results of subproblems so you never solve the same subproblem twice. That one idea — remember what you've already computed — is the entire heart of it.

The Two Properties That Make DP Work

Not every problem can be solved with DP. Two properties need to be present.

The first is overlapping subproblems: the problem breaks into smaller subproblems, and those subproblems repeat. Fibonacci is the textbook case — fib(48) shows up as a subproblem of both fib(50) and fib(49). If every subproblem were unique (like in merge sort, where you split the array in half and each half is distinct), storing results wouldn't help much.

The second is optimal substructure: the optimal solution to the big problem can be built from the optimal solutions to its subproblems. For Fibonacci this is trivially true — the correct value of fib(n) depends only on the correct values of fib(n-1) and fib(n-2). In optimization problems (shortest path, maximum profit), optimal substructure means you don't need to second-guess the smaller answers once you have them.

When both properties hold, DP applies.

Two Ways to Do DP: Memoization and Tabulation

There are two standard implementations, and they are equally valid. Pick whichever feels clearer for the problem at hand.

Memoization (top-down) keeps the recursive structure of the naive solution but adds a cache — typically a dictionary or array — to record each answer the first time it's computed. Before doing any work, you check the cache. If the answer is already there, return it immediately.

memo = {}
fib(n):
    if n <= 2: return 1
    if n in memo: return memo[n]
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Now fib(50) computes each value from fib(3) up to fib(50) exactly once — 48 real computations instead of a trillion.

About This Book

If you are looking for dynamic programming explained for beginners — without a PhD's worth of theory in the way — this book is for you. Concretely: you are a high school student who has hit recursion and wants to go further, a college freshman working through an intro to dynamic programming college course, or someone prepping for technical interviews who needs a focused algorithms study guide for high school students and early undergrads.

The book covers the core patterns: recurrence relations step by step, 1D problems like Coin Change and Longest Increasing Subsequence, and 2D problems including grid traversal, knapsack, and LCS. These are exactly the knapsack and LCS problems for students that appear on computer science exam prep and coding interview DP problems practice. A concise overview with no filler.

Read it straight through. Work every example in the text as you hit it, then attempt the problem set at the end to confirm you can apply what you learned under pressure.

Keep reading

You've read the first half of Chapter 1. The complete book covers 5 chapters in roughly fifteen pages — readable in one sitting.

Coming soon to Amazon