Recursion and Dynamic Programming

Recursion in one minute

A recursive function calls itself on a smaller problem. It needs two parts:

A base case that stops the calls.
A recursive case that moves toward the base case.

func power(_ base: Int, _ exponent: Int) -> Int {
    if exponent == 0 { return 1 }                  // base case
    let half = power(base, exponent / 2)           // smaller problem
    return exponent % 2 == 0 ? half * half : half * half * base
}

print(power(2, 10))   // 1024

This takes O(log n) calls instead of O(n), because the exponent halves each time.

Backtracking

Backtracking builds answers step by step: choose, explore, un-choose. Use it for "all subsets", "all permutations", "all combinations" and puzzles.

func subsets(_ nums: [Int]) -> [[Int]] {
    var result: [[Int]] = []
    var current: [Int] = []

    func build(from start: Int) {
        result.append(current)                // every path is a subset
        for i in start..<nums.count {
            current.append(nums[i])           // choose
            build(from: i + 1)                // explore
            current.removeLast()              // un-choose
        }
    }

    build(from: 0)
    return result
}

print(subsets([1, 2, 3]))
// [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

func permutations(_ nums: [Int]) -> [[Int]] {
    var result: [[Int]] = []
    var current: [Int] = []
    var used = Array(repeating: false, count: nums.count)

    func build() {
        if current.count == nums.count {
            result.append(current)
            return
        }
        for i in nums.indices where !used[i] {
            used[i] = true
            current.append(nums[i])
            build()
            current.removeLast()
            used[i] = false
        }
    }

    build()
    return result
}

print(permutations([1, 2, 3]).count)   // 6

A Swift bonus: arrays are values. result.append(current) stores a copy. In Java or Python you must copy by hand, or every saved answer changes later.

From recursion to dynamic programming

Dynamic programming (DP) is recursion plus remembering answers. Use it when the same smaller problem is solved many times.

Plain Fibonacci makes about 2^n calls, because it solves fib(n - 2) again and again:

func fibSlow(_ n: Int) -> Int {
    n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2)
}

Memoization with a dictionary (top-down)

Memoization means: save each answer the first time, and reuse it. Put the memo in the outer function, and the recursion in a nested function.

func fib(_ n: Int) -> Int {
    var memo: [Int: Int] = [:]

    func solve(_ n: Int) -> Int {
        if n < 2 { return n }
        if let saved = memo[n] { return saved }
        let answer = solve(n - 1) + solve(n - 2)
        memo[n] = answer
        return answer
    }

    return solve(n)
}

print(fib(50))   // 12586269025

Now each n is solved once: O(n) time and O(n) space.

Two or more parameters

Tuples are not Hashable, so they cannot be dictionary keys. Use a small struct:

struct Cell: Hashable {
    let row: Int
    let col: Int
}

func uniquePaths(_ rows: Int, _ cols: Int) -> Int {
    var memo: [Cell: Int] = [:]

    func paths(_ row: Int, _ col: Int) -> Int {
        if row == rows - 1 || col == cols - 1 { return 1 }   // one straight path left
        let key = Cell(row: row, col: col)
        if let saved = memo[key] { return saved }
        let answer = paths(row + 1, col) + paths(row, col + 1)
        memo[key] = answer
        return answer
    }

    return paths(0, 0)
}

print(uniquePaths(3, 7))   // 28

When the parameters are small integers, an array of optionals is faster than a dictionary:

var table = Array(repeating: Array(repeating: Int?.none, count: 7), count: 3)
table[1][2] = 10
print(table[1][2] as Any, table[0][0] as Any)   // Optional(10) nil

Bottom-up tables

Bottom-up DP fills a table from the smallest problems to the biggest. No recursion, so no risk of a stack overflow.

func climbStairs(_ n: Int) -> Int {
    guard n > 1 else { return 1 }
    var ways = Array(repeating: 0, count: n + 1)   // ways[i] = ways to reach step i
    ways[0] = 1
    ways[1] = 1
    for i in 2...n {
        ways[i] = ways[i - 1] + ways[i - 2]        // last move was 1 step or 2 steps
    }
    return ways[n]
}

print(climbStairs(5))   // 8

Each value only needs the last two. So you can keep two variables instead of the table:

func climbStairsSmall(_ n: Int) -> Int {
    guard n > 1 else { return 1 }
    var (twoBack, oneBack) = (1, 1)
    for _ in 2...n {
        (twoBack, oneBack) = (oneBack, twoBack + oneBack)
    }
    return oneBack
}

print(climbStairsSmall(5))   // 8

Careful: 2...n crashes when n < 2. That is why the guard comes first.

Five steps for any DP problem

Say these steps out loud. They structure your answer:

State: what does dp[i] (or dp[i][j]) mean? Write it in one sentence.
Transition: how is dp[i] built from smaller states?
Base cases: the smallest states you know directly.
Order: fill the table so that smaller states come first.
Answer: which cell holds the final answer?

Common DP shapes

1. Linear: one index

House robber: you cannot take two neighboring houses.

func rob(_ houses: [Int]) -> Int {
    var skipLast = 0   // best total if we did not take the previous house
    var takeLast = 0   // best total if we did take it
    for money in houses {
        (skipLast, takeLast) = (max(skipLast, takeLast), skipLast + money)
    }
    return max(skipLast, takeLast)
}

print(rob([2, 7, 9, 3, 1]))   // 12: 2 + 9 + 1

2. Grid: two indices

func minPathSum(_ grid: [[Int]]) -> Int {
    let rows = grid.count
    let cols = grid[0].count
    var dp = grid                       // dp[r][c] = cheapest cost to reach (r, c)
    for r in 0..<rows {
        for c in 0..<cols {
            if r == 0 && c == 0 { continue }
            let fromTop = r > 0 ? dp[r - 1][c] : Int.max
            let fromLeft = c > 0 ? dp[r][c - 1] : Int.max
            dp[r][c] += min(fromTop, fromLeft)
        }
    }
    return dp[rows - 1][cols - 1]
}

print(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))   // 7

3. Two sequences: prefixes of both

dp[i][j] is the answer for the first i characters of one string and the first j of the other. The table has one extra row and column for "empty".

func longestCommonSubsequence(_ a: String, _ b: String) -> Int {
    let x = Array(a)
    let y = Array(b)
    var dp = Array(repeating: Array(repeating: 0, count: y.count + 1), count: x.count + 1)
    for i in 0..<x.count {
        for j in 0..<y.count {
            dp[i + 1][j + 1] = x[i] == y[j]
                ? dp[i][j] + 1                           // same letter: extend
                : max(dp[i][j + 1], dp[i + 1][j])        // skip one letter
        }
    }
    return dp[x.count][y.count]
}

print(longestCommonSubsequence("abcde", "ace"))   // 3

Edit distance has the same shape:

func editDistance(_ a: String, _ b: String) -> Int {
    let x = Array(a)
    let y = Array(b)
    var dp = Array(repeating: Array(repeating: 0, count: y.count + 1), count: x.count + 1)
    for i in 0...x.count { dp[i][0] = i }   // delete every letter
    for j in 0...y.count { dp[0][j] = j }   // insert every letter
    for i in 0..<x.count {
        for j in 0..<y.count {
            dp[i + 1][j + 1] = x[i] == y[j]
                ? dp[i][j]
                : 1 + min(dp[i][j],          // replace
                          dp[i][j + 1],      // delete
                          dp[i + 1][j])      // insert
        }
    }
    return dp[x.count][y.count]
}

print(editDistance("horse", "ros"))   // 3

Looping with 0..<count and writing to i + 1 keeps the code safe for empty strings.

4. Knapsack: a budget

Use each item once (0/1 knapsack). Go through the sums from high to low, so an item is not used twice in the same round.

// Can the numbers be split into two groups with the same sum?
func canPartition(_ nums: [Int]) -> Bool {
    let total = nums.reduce(0, +)
    guard total % 2 == 0 else { return false }
    let target = total / 2
    var reachable = Array(repeating: false, count: target + 1)   // reachable[s]: some subset sums to s
    reachable[0] = true
    for n in nums {
        for sum in stride(from: target, through: n, by: -1) where reachable[sum - n] {
            reachable[sum] = true
        }
    }
    return reachable[target]
}

print(canPartition([1, 5, 11, 5]))   // true: [1, 5, 5] and [11]

Use items many times (unbounded). Go through the amounts from low to high:

func coinChange(_ coins: [Int], _ amount: Int) -> Int? {
    var fewest = Array(repeating: Int.max, count: amount + 1)   // fewest[a]: coins to make a
    fewest[0] = 0
    for value in stride(from: 1, through: amount, by: 1) {
        for coin in coins where coin <= value && fewest[value - coin] != Int.max {
            fewest[value] = min(fewest[value], fewest[value - coin] + 1)
        }
    }
    return fewest[amount] == Int.max ? nil : fewest[amount]
}

print(coinChange([1, 2, 5], 11)!)   // 3: 5 + 5 + 1
print(coinChange([2], 3) as Any)    // nil

Watch out for Int.max + 1. Swift crashes on overflow, so check for Int.max before you add.

5. Subsequence ending at i

// Longest strictly increasing subsequence.
func lengthOfLIS(_ nums: [Int]) -> Int {
    var best = Array(repeating: 1, count: nums.count)   // best[i]: longest one that ends at i
    for i in nums.indices {
        for j in 0..<i where nums[j] < nums[i] {
            best[i] = max(best[i], best[j] + 1)
        }
    }
    return best.max() ?? 0
}

print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))   // 4: [2, 3, 7, 18]

That is O(n²). A common follow-up asks for O(n log n). The idea: keep the smallest tail for each length. Place each number with the lower bound binary search from the Patterns chapter.

Shapes at a glance

Shape	State	Examples
Linear	`dp[i]`	Climbing stairs, house robber, decode ways
Grid	`dp[r][c]`	Unique paths, minimum path sum
Two sequences	`dp[i][j]` over prefixes	Longest common subsequence, edit distance
Knapsack	`dp[sum]`	Partition, coin change, target sum
Ending at i	`dp[i]` = best answer that ends at i	Longest increasing subsequence
Interval	`dp[left][right]`	Palindrome substrings, burst balloons

Top-down or bottom-up?

	Top-down (memo)	Bottom-up (table)
Easy to write	Yes, it follows the recursion	You must find the fill order
Computes	Only the states it needs	Every state
Deep inputs	Can overflow the stack	Safe
Saving memory	Hard	Easy: keep only the last row

A good interview flow: "First I'll write the plain recursion. Then I'll add a memo to make it O(n). If you want, I can turn it into a table and cut the space to O(1)."

#Recursion in one minute

#Backtracking

#From recursion to dynamic programming

#Memoization with a dictionary (top-down)

#Two or more parameters

#Bottom-up tables

#Five steps for any DP problem

#Common DP shapes

#1. Linear: one index

#2. Grid: two indices

#3. Two sequences: prefixes of both

#4. Knapsack: a budget

#5. Subsequence ending at i

#Shapes at a glance

#Top-down or bottom-up?