What is dynamic programming?

Q: What is dynamic programming?

**Target Audience:** Beginners preparing for coding interviews; you should be comfortable with functions, loops and recursion. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A teacher writes `1 + 1 + 1 + 1 + 1 + 1 + 1 + 1` on the board and asks the class for the total. Everyone counts and says "eight". Then she adds one more `+ 1` at the end and asks again. Nobody counts again from the beginning: everyone says "nine" straight away, because they **remembered** the eight and only did one more addition. That reflex — *do not redo work you have already done; w

The problem

Question presented to candidate: "What is dynamic programming? Explain it in your own words, then show me in Python how you would turn a slow recursive Fibonacci into a dynamic-programming solution, and tell me when you would reach for DP at all."

What a strong answer should cover:

DP = solve each overlapping subproblem once and reuse the stored answer; it needs overlapping subproblems and optimal substructure.
The two styles: memoization (top-down: recursion + cache) and tabulation (bottom-up: fill a table in dependency order), plus the rolling-variable space optimisation.
The five-step recipe: state, recurrence, base cases, order, answer — and the running-time formula states × work per state.
Why plain recursion is exponential (about 2.7 million calls for fib(30)) and DP is O(n).
Python specifics: a dict or functools.cache as the memo, the 1000-frame default recursion limit that breaks deep memoized recursion, arbitrary-precision int, and the mutable-default-argument trap (memo={}).

Code / implementation expected: Optional — a short Python function (memoized or tabulated Fibonacci) is the usual illustration; the explanation matters more than the code.

dynamic-programming

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should be comfortable with functions, loops and recursion. Difficulty: Medium Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A teacher writes 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 on the board and asks the class for the total. Everyone counts and says "eight". Then she adds one more + 1 at the end and asks again. Nobody counts again from the beginning: everyone says "nine" straight away, because they remembered

The solution is hidden so you can try first

9 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonFibonacci four ways: naive recursion, memoization, a table and two variables, with call counts

Practice

PythonOverlapping subproblems: how often naive recursion re-solves each fib(k), and the finished table

Practice

PythonThe DP recipe on a new problem: fewest perfect squares, where greedy fails