Computer Science Roadmap

Learn computing fundamentals, programming, algorithms, systems, and software engineering.

Overall Progress0%

Dynamic Programming

Explanation

Dynamic Programming (DP) is a technique for solving problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the answer so it is never recomputed. The name is misleading — it has nothing to do with "dynamic" in the everyday sense; it means solving a problem by filling in a table of saved results. The classic introduction is Fibonacci. A naive recursive solution computes the same values again and again and becomes impossibly slow. DP fixes this with one simple idea: remember the answers you have already found. There are two ways to fill the table. Memoization starts at the top and caches results as recursion returns. Tabulation builds the table bottom-up, from the smallest cases to the answer. Both give the same result; they differ only in direction. This lesson shows you how to recognise a DP problem, how to define the state, and how to move from a slow recursion to a fast, correct solution.

What Is Dynamic Programming?

Dynamic Programming solves a problem by splitting it into overlapping subproblems, solving each one once, and caching the results. It applies when a problem has two properties: optimal substructure and overlapping subproblems.

Overlapping subproblems: the same smaller problem appears many times.
Optimal substructure: the best solution is built from the best solutions to its parts.

Overlapping Subproblems: Fibonacci

Fibonacci is defined as F(n) = F(n-1) + F(n-2). Naive recursion recomputes the same values exponentially many times.

text

1F(5) calls F(4) and F(3)2F(4) calls F(3) and F(2)3F(3) calls F(2) and F(1)4 5F(3) and F(2) are computed over and over — wasted work.

Optimal Substructure

A problem has optimal substructure when the optimal answer can be built from optimal answers to its subproblems. In Fibonacci, F(5) is built from F(4) and F(3); if those are correct, F(5) is correct.

Recursion vs Dynamic Programming

	Plain recursion	Dynamic Programming
Repeated work	Recomputes subproblems	Computes each once
Memory	Call stack only	A table of saved results
Time	Often exponential	Usually polynomial
Typical use	Divide-and-conquer (no overlap)	Overlapping subproblems

Memoization (Top-Down)

Memoization keeps the recursive structure but stores each result in a cache, returning the saved value instead of recomputing.

python

1from functools import lru_cache2 3@lru_cache(maxsize=None)4def fib(n):5    if n <= 1:6        return n7    return fib(n - 1) + fib(n - 2)

Tabulation (Bottom-Up)

Tabulation fills an array from the base cases upward, eliminating recursion entirely.

python

1def fib(n):2    dp = [0, 1]3    for i in range(2, n + 1):4        dp.append(dp[i - 1] + dp[i - 2])5    return dp[n]

Defining State and Transitions

The "state" is the information that fully describes a subproblem. For Fibonacci the state is just n. The "transition" is the rule that combines smaller states into a bigger one.

State: what do I need to know to describe a subproblem?
Transition: how does one state lead to the next?
Base case: the smallest states with known answers.

How to Recognise a DP Problem

The problem asks for "the maximum/minimum/count" of something.
Solving a bigger case clearly reuses solutions to smaller cases.
There are choices at each step (take it or leave it).
A recursive solution exists but recomputes the same work.

Syntax

Fibonacci three wayspython

1# Naive (exponential)2def fib_naive(n):3    return n if n <= 1 else fib_naive(n - 1) + fib_naive(n - 2)4 5# Memoization6from functools import lru_cache7@lru_cache(maxsize=None)8def fib_memo(n):9    return n if n <= 1 else fib_memo(n - 1) + fib_memo(n - 2)10 11# Tabulation12def fib_tab(n):13    a, b = 0, 114    for _ in range(n):15        a, b = b, a + b16    return a

Memoization and tabulation are both O(n); the naive version is exponential.

Examples

Coin change

Find the fewest coins that sum to a given amount. The state is the remaining amount.

python

1def coin_change(coins, amount):2    dp = [float("inf")] * (amount + 1)3    dp[0] = 04    for a in range(1, amount + 1):5        for c in coins:6            if c <= a:7                dp[a] = min(dp[a], dp[a - c] + 1)8    return dp[amount] if dp[amount] != float("inf") else -19 10print(coin_change([1, 5, 10], 12))

Output

Memoization in action

fib_memo(30) is instant because each value is computed once.

python

1from functools import lru_cache2@lru_cache(maxsize=None)3def fib(n):4    return n if n <= 1 else fib(n - 1) + fib(n - 2)5print(fib(30))

Output

Key Takeaways

Dynamic Programming solves overlapping subproblems once and reuses the answers.
It requires optimal substructure: optimal answers are built from optimal sub-answers.
Memoization is top-down with a cache; tabulation is bottom-up with a table.
The state fully describes a subproblem; the transition combines states.
Fibonacci, coin change, and knapsack are the classic examples.

← PreviousSorting & Searching Next →Computer Architecture