readyforhires
Sign up free

Dynamic Programming 101

Advanced · 4 chapters · 9 min read · Define the state, write the recurrence, and let a table remember every subproblem.

Practise this in the app All guides

What dynamic programming really is

Recursion plus memory

Dynamic programming (DP) solves a problem by breaking it into overlapping subproblems, solving each one once, and storing the result. If a plain recursive solution keeps recomputing the same calls (Fibonacci is the classic example: fib(5) calls fib(3) twice and fib(2) three times), DP turns that exponential tree into a linear or quadratic table.

Two properties tell you DP applies:

  1. Optimal substructure: the best answer for the whole is built from best answers to smaller parts.
  2. Overlapping subproblems: the same smaller parts are needed again and again.

Signals in a problem statement

The four-step recipe

  1. State: what does dp[i] (or dp[i][j]) mean, in one precise sentence? For example, "dp[i] is the number of ways to decode the first i characters".
  2. Transition: how is dp[i] built from smaller states?
  3. Base cases: the smallest states whose answer you know directly.
  4. Order and answer: fill states so that dependencies are ready first, and say which state holds the final answer.

Most of the difficulty is step 1. Once the state sentence is right, the transition usually follows from asking "what was the last choice made?"

Core patterns with templates

1. Top-down with memoisation

from functools import lru_cache

def min_cost_climb(cost):
    @lru_cache(maxsize=None)
    def f(i):
        if i >= len(cost):
            return 0
        return cost[i] + min(f(i + 1), f(i + 2))
    return min(f(0), f(1))

2. Bottom-up 1D with rolling variables

def tribonacci(n):
    a, b, c = 0, 1, 1
    for _ in range(n):
        a, b, c = b, c, a + b + c
    return a

3. Counting ways over a string

def num_decodings(s):
    prev2, prev = 1, int(s[0] != "0")   # dp[i-2], dp[i-1]
    for i in range(1, len(s)):
        cur = prev if s[i] != "0" else 0
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            cur += prev2
        prev2, prev = prev, cur
    return prev

Example: "226" decodes as 2-2-6, 22-6 and 2-26, so the answer is 3.

4. Segmenting with a dictionary

def word_break(s, words):
    wset = set(words)
    dp = [True] + [False] * len(s)   # dp[i]: first i chars can be split
    for i in range(1, len(s) + 1):
        dp[i] = any(dp[j] and s[j:i] in wset for j in range(i))
    return dp[-1]

5. Two sequences (2D table)

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Edit distance uses the same table: on a match copy the diagonal, otherwise 1 + min(insert, delete, replace), with dp[i][0] = i and dp[0][j] = j.

6. Longest increasing subsequence in O(n log n)

from bisect import bisect_left

def lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

tails[k] is the smallest possible tail of an increasing subsequence of length k + 1.

Complexity, mistakes and edge cases

Complexity

Time is roughly number of states × work per state. Space is the number of states you keep.

ProblemStatesTimeSpace (optimised)
Climbing stairs, tribonaccinO(n)O(1)
Decode waysnO(n)O(1)
Word breaknO(n²) substring checksO(n)
Unique paths in a gridm × nO(mn)O(n) one row
LCS, edit distancem × nO(mn)O(min(m, n))
LIS (patience method)nO(n log n)O(n)

Common mistakes

Edge cases

Empty strings, a single element, all equal values (LIS of length 1), strings with zeros, a word list where no split works, grids with one row or one column, and identical input strings for edit distance (answer 0).

Grid paths

def unique_paths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[-1]

Each cell is the sum of the cell above (the old row[j]) and the cell to the left (the new row[j - 1]), so one row is enough.

Variations and practise

The families you will meet

How interviewers twist it

They ask you to reconstruct the answer, not just its value: keep the table and walk backwards from the final state, choosing whichever transition produced the stored value. They ask for less memory: roll the table into one or two rows. They change counting to modulo 10⁹ + 7: apply the modulo at each addition.

How to explain it

Write the state sentence and the recurrence as comments first, for example # dp[i][j] = edits to turn a[:i] into b[:j]. Then the base cases. Interviewers often give most of the credit at this point, before any loop is written.

Practise

The problems below start with one-dimensional warm-ups (tribonacci, cheapest stairs), move to counting decodings and segmenting words, then grid paths, and finish with the two-sequence classics (common subsequence and edit distance) and the longest increasing subsequence. Solve each first top-down with memoisation, then convert it to a bottom-up table.

Practise

Easy

Medium

Hard

Practise this in the app All guides