Dynamic Programming Field Notes

0Why dynamic programming exists

NeetCode says it plainly: DP is considered one of the hardest topics in CS, mostly because people overcomplicate it. Some DP problems are very hard, but the concept is not. Dynamic programming (DP) is an optimized version of recursion. You take a big problem, break it into smaller problems, and make sure each small problem is solved only once. That is usually better in time, and often in space, than plain recursion.

Start with the recursion you already know. Fibonacci, F(n) = F(n-1) + F(n-2):

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

Every call makes two more calls, so each level of the call tree doubles. Time is O(2ⁿ). Look at the tree for bruteForce(5) and count how often the same subtree appears.

Two words you need for the rest of the page. A subproblem is a smaller copy of the same question: F(3) is a subproblem of F(5). Subproblems are overlapping when the same one is asked more than once. Overlapping subproblems are the signal that DP will help.

11-D DP, top-down: recursion plus a cache

Memoization is a fancy word for caching

Memoization means: once a computation is done, store the result in a cache (a hash map or an array). If the same computation is asked again, retrieve it from the cache instead of recomputing. For fibonacci the hash map key is the index n and the value is F(n). A hash map lookup is O(1).

Recursion with memoization is called top-down DP, because you still start at the root of the tree (F(5)) and recurse down to the base cases. Only three lines change compared with the brute force:

def memoization(n, cache):
    if n <= 1:
        return n
    if n in cache:               # ② new base case: already solved? return it
        return cache[n]

    cache[n] = memoization(n - 1, cache) + memoization(n - 2, cache)
    return cache[n]               # ③ store, then return

memoization(5, {})                # ① the cache is passed in as a parameter → 5

1. Add a cache parameter (a hash map).
2. Add a base case: if n is in the cache, return the cached value instead of recursing.
3. After computing F(n), store it in the cache before returning.

Time O(n): each fibonacci number is computed once. Space O(n): the cache holds up to n entries, and the recursion stack is also n deep at its deepest point.

In real Python: functools.cache

Python ships the cache as a decorator. @lru_cache(maxsize=None) or the shorter @cache (Python 3.9+) wraps a function so that every call with the same arguments returns the stored result. You write the brute force and add one line above it.

from functools import lru_cache, cache

@lru_cache(maxsize=None)          # unlimited cache, keyed by the arguments
def fib_lru(n):
    if n <= 1:
        return n
    return fib_lru(n - 1) + fib_lru(n - 2)

@cache                            # same thing, shorter (3.9+)
def fib_cache(n):
    if n <= 1:
        return n
    return fib_cache(n - 1) + fib_cache(n - 2)

fib_cache(100)                    # 354224848179261915075, instantly
fib_lru.cache_info()              # shows hits and misses - proof the cache is working

21-D DP, bottom-up: fill a table, then shrink it

Tabulation: base cases first, work up

Top-down starts at F(5) and asks for smaller values. Bottom-up DP (also called tabulation) goes the other way: compute the base cases first, then use them to build the next value, and so on up to n. No recursion. Use an array of size n + 1 where index i holds F(i). For n = 5 the finished array is [0, 1, 1, 2, 3, 5].

def tabulation(n):
    if n < 2:
        return n
    table = [0] * (n + 1)         # index i will hold F(i)
    table[1] = 1                  # base cases: table[0] = 0, table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

Do we need the whole array? Only the last two

Look at the arrows in the picture: cell 5 reads only cells 3 and 4. Cells 0, 1, 2 are never touched again. We only ever use the previous two values, so keep just those two and compute in order. NeetCode uses an array of size 2, dp = [F(i-2), F(i-1)], and slides it forward with a temporary variable: store dp[1] in tmp, compute the next number into dp[1], then overwrite dp[0] with tmp. Space drops to O(1).

def dp(n):
    if n < 2:
        return n

    dp = [0, 1]                  # [F(0), F(1)]  - only two slots, ever
    i = 2
    while i <= n:
        tmp = dp[1]               # ① remember F(i-1) before it is overwritten
        dp[1] = dp[0] + dp[1]     # ② F(i) = F(i-2) + F(i-1)
        dp[0] = tmp               # ③ slide: old F(i-1) becomes the new "two back"
        i += 1
    return dp[1]

The idiomatic Python version

Python's tuple assignment evaluates the whole right side before assigning, so tmp disappears. Same algorithm, same O(n) time and O(1) space.

def fib_two_vars(n):
    a, b = 0, 1                  # a = F(i), b = F(i+1)
    for _ in range(n):
        a, b = b, a + b           # slide both by one; right side computed first
    return a

32-D DP: unique paths in a grid

When the result of a subproblem depends on two variables, the cache is a grid instead of a list: that is 2-D DP. The problem from the lesson: count the number of unique paths from the top-left to the bottom-right of a grid with rows rows and cols columns, moving only down or right. Because you only ever increase r or c, the only way to leave the grid is r == rows or c == cols.

Brute force: two choices per step

From (0, 0) you have at most two choices, down or right. The number of unique paths from a coordinate is the sum of the two recursive calls. Base cases: out of bounds returns 0 (that path is dead), the bottom-right cell returns 1 (one complete path).

# Brute Force - Time: O(2 ^ (n + m)), Space: O(n + m)
def bruteForce(r, c, rows, cols):
    if r == rows or c == cols:          # fell off the grid → 0 paths
        return 0
    if r == rows - 1 and c == cols - 1:  # reached the target → 1 path
        return 1

    return (bruteForce(r + 1, c, rows, cols) +   # go down
            bruteForce(r, c + 1, rows, cols))     # go right

bruteForce(0, 0, 4, 4)     # 20

Top-down: cache the answer for each coordinate

Same code plus a cache parameter. The cache is a rows × cols grid of zeros, and cache[r][c] stores the number of unique paths from that coordinate. NeetCode checks cache[r][c] > 0 to mean "already computed"; that works here because every in-bounds cell has at least one path, so 0 can only mean "not yet computed".

# Memoization - Time and Space: O(n * m)
def memoization(r, c, rows, cols, cache):
    if r == rows or c == cols:
        return 0
    if cache[r][c] > 0:                 # already solved this coordinate
        return cache[r][c]
    if r == rows - 1 and c == cols - 1:
        return 1

    cache[r][c] = (memoization(r + 1, c, rows, cols, cache) +
                   memoization(r, c + 1, rows, cols, cache))
    return cache[r][c]

cache = [[0] * 4 for _ in range(4)]   # rows x cols grid of zeros
memoization(0, 0, 4, 4, cache)         # 20

Bottom-up: start from the target, build rows upward

The picture above tells you the iterative order. Values become known from the bottom-right, so the loop must run bottom to top and, inside each row, right to left. Order matters because every value comes from the base-case side: below and to the right. And just like fibonacci, you do not need the whole grid in memory. To compute a row you only need the row below it. Keep two rows: prevRow (the row below) and curRow (the one being built). When a row is finished, it becomes the new prevRow.

# Dynamic Programming - Time: O(n * m), Space: O(m), where m is num of cols
def dp(rows, cols):
    prevRow = [0] * cols                       # imaginary row below the grid: all 0

    for r in range(rows - 1, -1, -1):           # bottom row first, up to row 0
        curRow = [0] * cols
        curRow[cols - 1] = 1                   # right-most column is the base case: 1
        for c in range(cols - 2, -1, -1):       # right to left
            curRow[c] = curRow[c + 1] + prevRow[c]  # right neighbor + cell below
        prevRow = curRow                        # slide up
    return prevRow[0]                           # top-left of the last row built

dp(4, 4)    # 20

Trace of dp(3, 3), every row. The answer for a 3 × 3 grid is 6; for 4 × 4 it is 20; for 3 × 7 it is 28.

The idiomatic top-down version

With @cache the coordinate pair (r, c) becomes the dictionary key automatically, and the "is it cached?" check disappears from your code. A nested function keeps rows and cols in scope so the cache key stays small.

from functools import cache

def uniquePaths_cache(rows, cols):
    @cache
    def go(r, c):
        if r == rows or c == cols:
            return 0
        if r == rows - 1 and c == cols - 1:
            return 1
        return go(r + 1, c) + go(r, c + 1)
    return go(0, 0)

uniquePaths_cache(3, 7)    # 28

Top-down vs bottom-up, side by side

4The 4-step DP recipe

Both lessons follow the same four moves. This is the order to use in an interview, out loud, and you can stop at any step that is good enough for the constraints.

1. Write the brute-force recursion. Decide what one call means ("paths from (r, c)", "F(n)"), write the base cases, and write the choices as recursive calls added or compared together. This is the recurrence: the formula that relates a problem to its smaller copies.
2. Find the repeated subproblems. Draw the call tree for a small input. If the same call appears twice (F(2) three times, (1, 1) twice), you have overlapping subproblems and DP will pay off. The parameters that identify a call are the state: one number → 1-D, two numbers → 2-D.
3. Add a cache. Check the cache before recursing, store after computing. In Python: @cache, or an explicit dictionary / grid parameter. Time drops from exponential to (number of states) × (work per state).
4. Flip to bottom-up and shrink the space. Read the fill order off the cache picture (from the base cases toward the answer), replace recursion with loops, then keep only the rows or values the recurrence actually reads: two variables for fibonacci, two rows for the grid.

5Moves that solve most DP problems

The lessons teach fibonacci and unique paths. Interviews reuse the same two shapes with different words. Learn the shapes, and learn how to notice that a problem is one of them.

Move 1: The memo decorator (top-down template)

When to use: you have a correct recursion and it is too slow. Wrap it. Works for any number of state parameters, as long as they are hashable.

from functools import cache

def solve_with_memo(n):
    @cache
    def f(i):                       # f(i) = answer for state i
        if i <= 1:                  # base case(s)
            return i
        return f(i - 1) + f(i - 2)  # recurrence: combine smaller states
    return f(n)

Move 2: The 1-D "two back" family: dp[i] from dp[i-1] and dp[i-2]

When to use: a line of positions, and the answer at position i depends only on the one or two positions before it. Fibonacci, climbing stairs, house robber, min cost climbing stairs all have this shape. Keep two variables and slide.

# Climbing Stairs (LC 70): ways to reach the top taking 1 or 2 steps at a time
def climbStairs(n):
    one, two = 1, 1              # ways from step n, and from step n-1 (both 1)
    for _ in range(n - 1):
        one, two = one + two, one # exactly the fibonacci slide
    return one                    # climbStairs(5) → 8

# House Robber (LC 198): rob non-adjacent houses for the max total
def rob(nums):
    rob1, rob2 = 0, 0            # best total ending two back, and one back
    for n in nums:
        rob1, rob2 = rob2, max(rob1 + n, rob2)  # rob this house, or skip it
    return rob2                   # rob([2, 7, 9, 3, 1]) → 12

# Min Cost Climbing Stairs (LC 746): cheapest way past the last step
def minCostClimbingStairs(cost):
    a, b = 0, 0                  # min cost to stand on step i-2, i-1
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i - 1], a + cost[i - 2])
    return b                      # minCostClimbingStairs([10, 15, 20]) → 15

Move 3: The 2-D grid family: cell from below and right (or above and left)

When to use: a grid, moves restricted to two directions, and a question about counting or optimizing paths. Unique paths counts (plus), min path sum optimizes (min). Same two-row loop; only the combine step changes, and for a cost grid you add the cell's own value.

# Minimum Path Sum (LC 64): cheapest down/right path from top-left to bottom-right
def minPathSum(grid):
    rows, cols = len(grid), len(grid[0])
    prev = [float("inf")] * cols                # "below the grid" is impossible → infinity
    for r in range(rows - 1, -1, -1):
        cur = [0] * cols
        for c in range(cols - 1, -1, -1):
            if r == rows - 1 and c == cols - 1:
                cur[c] = grid[r][c]              # base case: the target itself
            else:
                right = cur[c + 1] if c + 1 < cols else float("inf")
                down = prev[c]
                cur[c] = grid[r][c] + min(right, down)   # min instead of +
        prev = cur
    return prev[0]      # minPathSum([[1,3,1],[1,5,1],[4,2,1]]) → 7

Move 4: How to spot DP in a problem statement

Three kinds of questions, each answered over a series of choices, are DP suspects:

• "How many ways" to reach / build / arrange something (unique paths, climbing stairs, coin change II). The recurrence adds.
• "Minimum or maximum" cost, length, profit, sum over a sequence of choices (min path sum, house robber, longest increasing subsequence, coin change). The recurrence takes min or max.
• "Is it possible / true or false" to reach a state (word break, partition equal subset sum). The recurrence uses or.

Then confirm the two conditions. Optimal substructure: the best answer for the big problem is built from best answers of smaller ones. Overlapping subproblems: the brute force asks the same smaller question more than once. If the second condition fails (every subproblem is different, like merge sort), plain recursion is already fine and a cache buys nothing.

6Big-O summary

n is the fibonacci index; for grids, n is rows and m is columns. The pattern is always the same: exponential brute force, then (number of states) for time, then shrink the space.

General rule to say in interviews: memoized time = (number of distinct states) × (work per state, not counting the recursive calls). Fibonacci: n states × O(1) = O(n). Grid: n · m states × O(1) = O(n · m).

7Mistakes to watch for

8Practice, in this order

Do each one in the four steps: brute force, find the repeat, add @cache, flip to bottom-up. Even when the easy version is enough, write the bottom-up version once. That is the muscle.

Your next step today: LeetCode 70, Climbing Stairs. Write the brute force, draw the tree for n = 5, add @cache, then write the two-variable loop from memory and compare with the fibonacci trace table.

9Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.