Lesson 6 of 6

Recursion, backtracking and dynamic programming

2 min read

Backtracking

Build a solution step by step; undo the last choice when it can't lead anywhere.

python

def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):
            out.append(path[:]); return
        path.append(nums[i]); go(i + 1)   # take it
        path.pop();           go(i + 1)   # skip it
    go(0)
    return out

Same skeleton for permutations, combination sum, N-Queens, word search and generating valid parentheses.

Dynamic programming

Use DP when a problem has overlapping subproblems (the same sub-question is asked many times) and optimal substructure (the best answer is built from best answers to smaller questions).

Steps:

Define the state: dp[i] = the answer for the first i items (or ending at i).
Write the recurrence: how dp[i] comes from smaller states.
Base cases.
Order of computation (top-down with memoisation, or bottom-up table).
Optimise space if only the last few states are needed.

Climbing stairs (1 or 2 steps): dp[i] = dp[i-1] + dp[i-2].

House robber (no two adjacent houses):

python

def rob(nums):
    take, skip = 0, 0
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)

Coin change (fewest coins):

python

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

Longest common subsequence (2D):

python

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

Common DP families: 1D sequences (stairs, robber, decode ways), knapsack (0/1, unbounded: coin change), two strings (LCS, edit distance), grids (unique paths, minimum path sum), intervals and LIS (longest increasing subsequence, O(n log n) with binary search).

Greedy

Make the locally best choice when you can prove it leads to the global best: interval scheduling (sort by end time), jump game, gas station, assigning cookies. If you can't justify the greedy choice, it's probably DP.

A 6-week practice plan

Week 1: arrays, hashing, prefix sums.
Week 2: two pointers, sliding window, binary search.
Week 3: stacks, queues, heaps, linked lists.
Week 4: trees.
Week 5: graphs, backtracking.
Week 6: DP and greedy, then mixed timed sets.

Do 2–3 problems a day. If stuck for 25 minutes, read the solution, then re-solve it from scratch the next day. Patterns stick through repetition, not volume.

← Previous