Data Structures, Algorithms and Programming Patterns · Part 7 of 9

Data Structures and Algorithms, Part 7: Recursion, Backtracking, Greedy Choices and Dynamic Programming

Some problems have too many possible answers to check one by one. This part shows four ways of handling them: recursion to break a problem into smaller copies, backtracking to explore choices and undo them, greedy steps when the best local choice is safe, and dynamic programming to stop solving the same subproblem twice.

1. Recursion: a function that calls itself

A recursive function is a function that calls itself to solve a smaller piece of the same problem. That sounds circular, but it works as long as the pieces keep getting smaller and there is a place to stop.

Every recursive function has two parts:

• The base case: the input so small that the answer is known without any more calls. It is the empty doll. Write it first.
• The recursive case: solve the problem by calling the same function on a smaller input, then combine the result with a little extra work.

If you forget the base case, or the input never gets smaller, the function calls itself forever. That is the number one recursion bug.

Three small examples

The factorial of n (written n!) is n * (n-1) * ... * 1. Notice that n! = n * (n-1)!. That is already a recursive rule. The base case is 1! = 1 (and 0! = 1).

The program below prints a line when each call starts and when it returns, indented by depth, so you can see the dolls opening and closing.

fun factorial(n: Int, depth: Int = 0): Long {
    val pad = " ".repeat(depth * 2)
    println("${pad}factorial($n) called")
    if (n <= 1) {                       // base case first
        println("${pad}base case, return 1")
        return 1
    }
    val result = n * factorial(n - 1, depth + 1)   // recursive case
    println("${pad}factorial($n) returns $result")
    return result
}

fun main() {
    println("answer = ${factorial(4)}")
}

The call stack

How does the computer remember where it was in each call? It uses the call stack: a pile of “frames”, one per active call. A frame holds that call’s own variables and the place to continue after it finishes. A new call puts a frame on top. A return removes the top frame. (A stack is last in, first out, as Part 3 explains.)

Sum and power

The sum of 1..n is n plus the sum of 1..n-1, with 0 as the base case. Power is more interesting. Computing b^e as b * b^(e-1) takes e calls. But b^e = (b^(e/2))^2 halves the exponent each time, so it takes only about log e calls. Halving is the same trick as binary search.

var slowCalls = 0
var fastCalls = 0

fun sumTo(n: Int): Int = if (n == 0) 0 else n + sumTo(n - 1)

// b^e as b * b^(e-1): e + 1 calls, O(e)
fun powerSlow(b: Long, e: Int): Long {
    slowCalls++
    return if (e == 0) 1 else b * powerSlow(b, e - 1)
}

// b^e as (b^(e/2))^2, times b once more if e is odd: O(log e)
fun powerFast(b: Long, e: Int): Long {
    fastCalls++
    if (e == 0) return 1
    val half = powerFast(b, e / 2)
    return if (e % 2 == 0) half * half else half * half * b
}

fun main() {
    println("sumTo(100) = ${sumTo(100)}")
    println("slow: ${powerSlow(2, 30)} in $slowCalls calls")
    println("fast: ${powerFast(2, 30)} in $fastCalls calls")
}

When the stack runs out

The call stack has a limited size. If recursion goes too deep (hundreds of thousands of frames, depending on the machine), the program stops with a stack overflow. In Kotlin and Java that is a StackOverflowError. It usually means a missing base case, or an input that is simply too deep for recursion.

There are two ways out. A tail call is a recursive call that is the very last thing a function does, with nothing left to do afterwards. Kotlin can turn those into a loop if you mark the function tailrec. The other way is to write the loop yourself. Any recursion can become a loop, and when the depth is huge, that is the safe choice.

fun depth(n: Int): Int = if (n == 0) 0 else 1 + depth(n - 1)   // work left after the call: not a tail call

tailrec fun sumTail(n: Long, acc: Long = 0): Long =           // the call is the last thing: a tail call
    if (n == 0L) acc else sumTail(n - 1, acc + n)

fun sumLoop(n: Long): Long {                                  // the same thing as a plain loop
    var total = 0L
    for (i in 1..n) total += i
    return total
}

fun main() {
    println("depth(1000) = ${depth(1000)}")
    try {
        println(depth(10_000_000))
    } catch (e: StackOverflowError) {
        println("StackOverflowError: ten million frames do not fit")
    }
    println("tailrec = ${sumTail(10_000_000)}")
    println("loop    = ${sumLoop(10_000_000)}")
}

2. Divide and conquer, a short recap

Divide and conquer is a recursion shape you may have met in sorting (Part 6): split the problem into smaller copies, solve each copy, combine the answers. Fast power did it with one half. Binary search does it with one half. Merge sort does it with two halves.

The key property is that the pieces do not overlap. Each half of the list is a different set of items, so no work is repeated. Remember this, because dynamic programming exists for the case where the pieces do overlap.

var calls = 0

fun maxRange(a: IntArray, lo: Int, hi: Int): Int {
    calls++
    if (lo == hi) return a[lo]                  // base case: one item
    val mid = (lo + hi) / 2
    val left = maxRange(a, lo, mid)             // solve the left half
    val right = maxRange(a, mid + 1, hi)        // solve the right half
    return maxOf(left, right)                   // combine
}

fun main() {
    val a = intArrayOf(4, 9, 2, 7, 5, 1, 8, 3)
    println("max = ${maxRange(a, 0, a.size - 1)}")
    println("calls = $calls  (n = ${a.size}, so about 2n - 1)")
}

The cost of a divide-and-conquer algorithm depends on two numbers: how many pieces you make, and how much work the combine step is. Splitting in two and combining in O(n) gives O(n log n), as in merge sort. Splitting in one half with O(1) combining gives O(log n), as in binary search.

3. Backtracking: try, look ahead, undo

Backtracking is recursion used to search through many possible answers. You build an answer one decision at a time. When a decision leads to a dead end, you undo it and try the next option.

A few words first. The state is whatever describes where you are in the search: the choices made so far. A decision tree is the picture of all the choices, where each level is one decision.

The template: choose, explore, un-choose

Nearly every backtracking solution has the same three steps inside a loop:

1. Choose: add one option to the current state.
2. Explore: recurse to make the next decision.
3. Un-choose: remove that option, so the state is exactly as it was before. This is the “back” in backtracking.

fun explore(state) {
    if (state is a complete answer) { save a COPY of it; return }
    for (option in options available now) {
        if (option is not allowed) continue   // pruning
        choose(option)
        explore(state)
        unchoose(option)
    }
}

Two details trip people up. First, when you save an answer, save a copy (current.toList()), because the same list keeps changing afterwards. Second, un-choose must exactly reverse choose.

Subsets and permutations

A subset is any selection of items, ignoring order. A permutation is an ordering of all the items. For three items there are 8 subsets and 6 permutations. In general, 2^n subsets and n! permutations, so these programs only work for small n.

fun subsets(nums: List<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val current = mutableListOf<Int>()

    fun explore(start: Int) {
        result.add(current.toList())               // every state on the way is a valid subset
        for (i in start until nums.size) {
            current.add(nums[i])                   // choose
            explore(i + 1)                         // explore: only look at later items
            current.removeAt(current.size - 1)     // un-choose
        }
    }

    explore(0)
    return result
}

fun main() {
    for (s in subsets(listOf(1, 2, 3))) println(s)
    println("count for 10 items = ${subsets(List(10) { it }).size}")
}

fun permutations(nums: List<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val current = mutableListOf<Int>()
    val used = BooleanArray(nums.size)

    fun explore() {
        if (current.size == nums.size) {           // complete answer
            result.add(current.toList())
            return
        }
        for (i in nums.indices) {
            if (used[i]) continue                  // already placed in this answer
            used[i] = true                         // choose
            current.add(nums[i])
            explore()                              // explore
            current.removeAt(current.size - 1)     // un-choose
            used[i] = false
        }
    }

    explore()
    return result
}

fun main() {
    for (p in permutations(listOf(1, 2, 3))) println(p)
    println("count for 6 items = ${permutations(List(6) { it }).size}")
}

Pruning: stop early when a branch cannot work

Pruning means cutting off a branch of the decision tree as soon as you know it cannot lead to a valid answer. It does not change the worst-case Big-O, but it can remove almost all the work in practice. Choosing 2 numbers out of 1..4 (a combination, a subset of a fixed size) can stop as soon as the list reaches size 2.

The classic example is the n-queens puzzle: place n queens on an n by n chessboard so that none attacks another. We place one queen per row. For each row we try every column, but skip any square whose column or diagonal is already taken. The skipped squares are the pruning.

fun countQueens(n: Int): Int {
    val cols = BooleanArray(n)
    val diagDown = BooleanArray(2 * n)       // squares with the same row + col
    val diagUp = BooleanArray(2 * n)         // squares with the same row - col (shifted)
    var count = 0

    fun place(row: Int) {
        if (row == n) { count++; return }    // all rows filled: one solution
        for (c in 0 until n) {
            val d1 = row + c
            val d2 = row - c + n
            if (cols[c] || diagDown[d1] || diagUp[d2]) continue   // prune: attacked square
            cols[c] = true; diagDown[d1] = true; diagUp[d2] = true     // choose
            place(row + 1)                                              // explore
            cols[c] = false; diagDown[d1] = false; diagUp[d2] = false   // un-choose
        }
    }

    place(0)
    return count
}

fun main() {
    for (n in 1..8) println("n = $n -> ${countQueens(n)} solutions")
}

4. Greedy: take the best choice now

A greedy algorithm makes the choice that looks best right now, never looks back, and never undoes it. There is no search and no recursion, usually just a sort and a loop, so greedy algorithms are fast and short.

The catch is that “best right now” is only correct for some problems. For the others, greedy gives a wrong answer without any warning. The skill is knowing which is which.

Coin change: greedy works, then it does not

Make 63 cents with the fewest coins. Take the biggest coin that fits, again and again. With coins 25, 10, 5, 1 that gives 25+25+10+1+1+1, six coins, and it is the best possible. Coin sets where this always works are called canonical. Most real currencies are designed that way.

Now change the coins to 1, 3, 4 and ask for 6. Greedy takes 4, then 1, then 1: three coins. But 3+3 is two coins. The locally best first step (the biggest coin) spoiled the whole answer.

// Greedy: biggest coin first. Returns the coin count, or -1 if it gets stuck.
fun greedyCoins(coins: List<Int>, amount: Int): Int {
    var left = amount
    var count = 0
    for (c in coins.sortedDescending()) {
        count += left / c
        left %= c
    }
    return if (left == 0) count else -1
}

// Exact answer by trying every coin for every amount (dynamic programming, explained soon).
fun bestCoins(coins: List<Int>, amount: Int): Int {
    val inf = amount + 1
    val dp = IntArray(amount + 1) { inf }
    dp[0] = 0
    for (a in 1..amount) for (c in coins) if (c <= a) dp[a] = minOf(dp[a], dp[a - c] + 1)
    return if (dp[amount] >= inf) -1 else dp[amount]
}

fun main() {
    val us = listOf(25, 10, 5, 1)
    println("63 with $us: greedy=${greedyCoins(us, 63)} best=${bestCoins(us, 63)}")
    val odd = listOf(1, 3, 4)
    println("6 with $odd: greedy=${greedyCoins(odd, 6)} best=${bestCoins(odd, 6)}")
}

Interval scheduling

You have a list of activities, each with a start and end time, and one room. Pick as many as possible so that none overlap. A tempting rule is “earliest start” or “shortest”, but both have counter-examples. The rule that is provably right: always pick the activity that ends earliest, because it leaves the most room for the rest. Sort by end time, then take each activity that starts after the last chosen one ends.

fun selectActivities(acts: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    val chosen = mutableListOf<Pair<Int, Int>>()
    var lastEnd = Int.MIN_VALUE
    for (a in acts.sortedBy { it.second }) {      // earliest end first
        if (a.first >= lastEnd) {                 // starts after the last pick ended
            chosen.add(a)
            lastEnd = a.second
        }
    }
    return chosen
}

fun main() {
    val acts = listOf(1 to 4, 3 to 5, 0 to 6, 5 to 7, 3 to 9, 5 to 9, 6 to 10, 8 to 11)
    val picked = selectActivities(acts)
    println("picked ${picked.size}: $picked")
}

Jump game

You stand at the start of an array. Each number says the longest jump you can make from that square. Can you reach the last square? Greedy view: walk left to right and track the farthest square reachable so far. If you ever stand on a square beyond that, you are stuck.

fun canJump(nums: IntArray): Boolean {
    var farthest = 0
    for (i in nums.indices) {
        if (i > farthest) return false            // this square is out of reach
        farthest = maxOf(farthest, i + nums[i])   // best landing spot seen so far
    }
    return true
}

fun main() {
    println(canJump(intArrayOf(2, 3, 1, 1, 4)))   // true
    println(canJump(intArrayOf(3, 2, 1, 0, 4)))   // false: every path ends on the 0
    println(canJump(intArrayOf(0)))               // true: already at the end
}

5. Dynamic programming: remember what you solved

Dynamic programming (DP) sounds mysterious, but the idea is plain: do not solve the same small problem twice. Solve it once, write the answer down, and look it up next time.

Two properties tell you DP can work:

• Overlapping subproblems. A subproblem is a smaller version of the same question. They overlap when the same subproblem is needed again and again by different bigger ones. (In divide and conquer they do not overlap.)
• Optimal substructure. The best answer to the big problem is built from the best answers to its subproblems.

The four steps

1. Define the state. Say in one sentence what dp[i] (or dp[i][j]) means. For example, “the fewest coins that make amount i”. This sentence is the most important line you write.
2. Write the recurrence. A recurrence is a formula that gets one state from smaller states, for example dp[i] = min(dp[i - coin] + 1) over all coins.
3. Set the base cases. The smallest states, whose answers you simply know: dp[0] = 0.
4. Choose the order. Fill states so that everything a state depends on is already filled. Usually that means smaller indexes first. The answer is the state for the full problem.

There are two ways to carry out the plan. Memoisation (top-down) keeps the recursive function and adds a notebook: before computing, check it; after computing, save it. Tabulation (bottom-up) drops the recursion and fills a table from the smallest state to the largest with loops.

6. Fibonacci four ways

The Fibonacci numbers start 0, 1, 1, 2, 3, 5, 8, ... and each is the sum of the two before. The state is fib(n), the recurrence is fib(n) = fib(n-1) + fib(n-2), and the base cases are fib(0) = 0, fib(1) = 1. Here is what the naive recursion does for fib(5):

The number of calls roughly multiplies by 1.6 for every step of n, so naive Fibonacci is exponential. The program below runs four versions and counts the calls.

var naiveCalls = 0L
var memoCalls = 0L
val memo = HashMap<Int, Long>()

// 1. Naive recursion: exponential time.
fun fibNaive(n: Int): Long {
    naiveCalls++
    return if (n < 2) n.toLong() else fibNaive(n - 1) + fibNaive(n - 2)
}

// 2. Top-down with a notebook (memoisation): O(n) time, O(n) space.
fun fibMemo(n: Int): Long {
    memoCalls++
    if (n < 2) return n.toLong()
    memo[n]?.let { return it }             // already solved: look it up
    val answer = fibMemo(n - 1) + fibMemo(n - 2)
    memo[n] = answer                       // write it in the notebook
    return answer
}

// 3. Bottom-up table (tabulation): O(n) time, O(n) space.
fun fibTable(n: Int): Long {
    if (n < 2) return n.toLong()
    val dp = LongArray(n + 1)
    dp[1] = 1
    for (i in 2..n) dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

// 4. Keep only the last two values: O(n) time, O(1) space.
fun fibTwoVars(n: Int): Long {
    var a = 0L
    var b = 1L
    repeat(n) { val next = a + b; a = b; b = next }
    return a
}

fun main() {
    val n = 30
    println("naive : ${fibNaive(n)}  calls = $naiveCalls")
    println("memo  : ${fibMemo(n)}  calls = $memoCalls")
    println("table : ${fibTable(n)}")
    println("2 vars: ${fibTwoVars(n)}")
    println("fib(90) = ${fibTwoVars(90)}")
}

The last step is a habit worth learning: when dp[i] only needs the previous one or two entries, you do not have to keep the whole table. Keep a few variables.

7. Classic one-dimensional problems

A one-dimensional DP has a single index in its state. We will do three, each following the four steps.

Climbing stairs

You can climb 1 or 2 steps at a time. How many different ways reach step n?

1. State: ways[i] = the number of ways to reach step i.
2. Recurrence: the last move was a 1-step from i-1 or a 2-step from i-2, so ways[i] = ways[i-1] + ways[i-2].
3. Base: ways[0] = 1 (do nothing), ways[1] = 1.
4. Order: i from 2 up to n.

It is Fibonacci in disguise. Spotting a familiar recurrence is a big part of the skill.

House robber

A row of houses holds some money each. You may not take from two neighbouring houses. What is the most you can take?

1. State: best[i] = the most money from the first i houses.
2. Recurrence: for house i, either skip it (best[i-1]) or take it and skip its neighbour (best[i-2] + money[i]). Choose the larger.
3. Base: no houses gives 0; one house gives its money.
4. Order: left to right. Only the last two values matter, so two variables are enough.

Coin change, fewest coins

The same coin problem greedy got wrong, now solved properly. State: fewest[a] = the fewest coins to make amount a. Recurrence: try each coin c as the last coin: fewest[a] = 1 + min(fewest[a - c]). Base: fewest[0] = 0. Order: amounts from 1 up to the target. Amounts that no coin combination can make stay at “infinity” and we report -1.

// Climbing stairs: ways[i] = ways[i-1] + ways[i-2]
fun climbStairs(n: Int): Long {
    var prev = 1L      // ways[0]
    var cur = 1L       // ways[1]
    for (i in 2..n) { val next = prev + cur; prev = cur; cur = next }
    return cur
}

// House robber: best[i] = max(best[i-1], best[i-2] + money[i])
fun rob(money: IntArray): Int {
    var twoBack = 0    // best for the houses up to i-2
    var oneBack = 0    // best for the houses up to i-1
    for (m in money) {
        val best = maxOf(oneBack, twoBack + m)
        twoBack = oneBack
        oneBack = best
    }
    return oneBack
}

// Coin change: fewest[a] = 1 + min over coins of fewest[a - coin]
fun coinChange(coins: IntArray, amount: Int): Int {
    if (amount < 0) return -1
    val inf = amount + 1                       // bigger than any real answer
    val fewest = IntArray(amount + 1) { inf }
    fewest[0] = 0
    for (a in 1..amount) {
        for (c in coins) {
            if (c <= a && fewest[a - c] + 1 < fewest[a]) fewest[a] = fewest[a - c] + 1
        }
    }
    return if (fewest[amount] >= inf) -1 else fewest[amount]
}

fun main() {
    println("stairs(5) = ${climbStairs(5)}, stairs(50) = ${climbStairs(50)}")
    println("rob = ${rob(intArrayOf(2, 7, 9, 3, 1))}")          // 2 + 9 + 1 = 12
    println("coins 1,3,4 for 6 = ${coinChange(intArrayOf(1, 3, 4), 6)}")   // 2
    println("coins 2 for 3     = ${coinChange(intArrayOf(2), 3)}")           // -1, impossible
    println("coins 5 for 0     = ${coinChange(intArrayOf(5), 0)}")           // 0
}

8. Two-dimensional problems and the filled table

When the state needs two numbers, the table has two dimensions. A common case is two sequences, where i is how much of the first you have used and j how much of the second.

Grid paths

A robot starts at the top-left of a grid and can only move right or down. How many routes reach the bottom-right? State: paths[r][c] = routes to square (r, c). Recurrence: you arrived from above or from the left, so paths[r][c] = paths[r-1][c] + paths[r][c-1]. Base: the first row and first column are all 1. Order: row by row.

Longest common subsequence

A subsequence keeps letters in order but may skip some, like ACD from ABCD. The longest common subsequence (LCS) of two strings is the longest one that appears in both. It is the idea behind file-comparison tools.

1. State: dp[i][j] = the LCS length of the first i letters of s and the first j letters of t.
2. Recurrence: if the letters s[i-1] and t[j-1] match, extend the diagonal: dp[i-1][j-1] + 1. Otherwise take the better of dropping a letter from either string: max(dp[i-1][j], dp[i][j-1]).
3. Base: with an empty string the answer is 0, so row 0 and column 0 are zeros.
4. Order: rows top to bottom, columns left to right.

fun gridPaths(rows: Int, cols: Int): Long {
    val paths = Array(rows) { LongArray(cols) }
    for (r in 0 until rows) for (c in 0 until cols) {
        paths[r][c] = if (r == 0 || c == 0) 1 else paths[r - 1][c] + paths[r][c - 1]
    }
    return paths[rows - 1][cols - 1]
}

fun lcsTable(s: String, t: String): Array<IntArray> {
    val dp = Array(s.length + 1) { IntArray(t.length + 1) }     // row 0 and column 0 stay 0
    for (i in 1..s.length) for (j in 1..t.length) {
        dp[i][j] = if (s[i - 1] == t[j - 1]) dp[i - 1][j - 1] + 1
                   else maxOf(dp[i - 1][j], dp[i][j - 1])
    }
    return dp
}

fun main() {
    println("grid 3x4 -> ${gridPaths(3, 4)}")
    println("grid 18x18 -> ${gridPaths(18, 18)}")
    val s = "ABCD"
    val t = "ACBD"
    val dp = lcsTable(s, t)
    for (row in dp) println(row.joinToString(" "))
    println("LCS length = ${dp[s.length][t.length]}")
}

Edit distance

The edit distance between two words is the fewest single-letter edits (insert, delete or replace) that turn one into the other. Spell checkers use it to suggest corrections. The shape is the same as LCS. State: dp[i][j] = the edits to turn the first i letters of a into the first j of b. Base: turning a word into an empty one costs its length (delete everything), and the reverse costs the other length (insert everything). Recurrence: if the letters match, copy the diagonal for free. Otherwise it is one edit plus the cheapest of three neighbours: diagonal (replace), above (delete), left (insert).

fun editDistance(a: String, b: String): Int {
    val dp = Array(a.length + 1) { IntArray(b.length + 1) }
    for (i in 0..a.length) dp[i][0] = i          // delete i letters
    for (j in 0..b.length) dp[0][j] = j          // insert j letters
    for (i in 1..a.length) for (j in 1..b.length) {
        dp[i][j] = if (a[i - 1] == b[j - 1]) {
            dp[i - 1][j - 1]                                             // match: free
        } else {
            1 + minOf(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])      // replace, delete, insert
        }
    }
    return dp[a.length][b.length]
}

fun main() {
    println(editDistance("kitten", "sitting"))   // 3
    println(editDistance("", "abc"))             // 3
    println(editDistance("same", "same"))        // 0
    println(editDistance("horse", "ros"))        // 3
}

9. Top-down or bottom-up?

Both styles give the same answers and the same Big-O in most problems. They differ in how you write them and what they cost in practice.

A practical path: write the recurrence as plain recursion, add a cache to see it work (top-down), then convert to loops and shrink the memory (bottom-up). You do not have to pick one for life.

// Count the ways to climb n stairs taking 1, 2 or 3 steps at a time.

// Top-down: recursion plus a cache.
fun waysTopDown(n: Int, cache: HashMap<Int, Long> = HashMap()): Long {
    if (n < 0) return 0
    if (n == 0) return 1
    cache[n]?.let { return it }
    val result = waysTopDown(n - 1, cache) + waysTopDown(n - 2, cache) + waysTopDown(n - 3, cache)
    cache[n] = result
    return result
}

// Bottom-up: a table filled from the smallest case.
fun waysBottomUp(n: Int): Long {
    val ways = LongArray(n + 1)
    ways[0] = 1
    for (i in 1..n) {
        for (step in 1..3) if (i - step >= 0) ways[i] += ways[i - step]
    }
    return ways[n]
}

fun main() {
    for (n in listOf(0, 1, 3, 10, 30)) {
        println("n=$n  top-down=${waysTopDown(n)}  bottom-up=${waysBottomUp(n)}")
    }
}

10. Choosing the right tool

You now have four ways of attacking a problem that has many possible answers. Use this table to decide, and then confirm on a small example.

A short routine for a new problem:

1. Write the brute-force recursion. Is it correct on small inputs?
2. Draw its call tree. Do the same arguments appear more than once? If so, add a cache (DP).
3. If you need the actual list of answers rather than a count or a best value, you are probably doing backtracking, and the answers themselves set the cost.
4. If sorting the input makes one simple rule work, test it against the brute force. If it never disagrees on many small cases, greedy may be right.

11. Practice

Six exercises, one for each idea in this part. Start with the state sentence on paper for the DP ones, and test small cases by hand first.

fun power(base: Long, exp: Int): Long {
    TODO("base case first, then use the half")
}

fun power(base: Long, exp: Int): Long {
    if (exp == 0) return 1
    val half = power(base, exp / 2)
    return if (exp % 2 == 0) half * half else half * half * base
}

fun combinations(n: Int, k: Int): List<List<Int>> {
    TODO("backtrack with a current list and a start number")
}

fun combinations(n: Int, k: Int): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val current = mutableListOf<Int>()
    fun explore(start: Int) {
        if (current.size == k) {
            result.add(current.toList())
            return
        }
        for (i in start..n) {
            current.add(i)
            explore(i + 1)
            current.removeAt(current.size - 1)
        }
    }
    explore(1)
    return result
}

fun canJump(nums: IntArray): Boolean {
    TODO("walk left to right, track the farthest square")
}

fun canJump(nums: IntArray): Boolean {
    var farthest = 0
    for (i in nums.indices) {
        if (i > farthest) return false
        farthest = maxOf(farthest, i + nums[i])
    }
    return true
}

fun rob(money: IntArray): Int {
    TODO("best so far = max(skip this house, take it plus best two back)")
}

fun rob(money: IntArray): Int {
    var twoBack = 0
    var oneBack = 0
    for (m in money) {
        val best = maxOf(oneBack, twoBack + m)
        twoBack = oneBack
        oneBack = best
    }
    return oneBack
}

fun minCoins(coins: IntArray, amount: Int): Int {
    TODO("fewest[a] = 1 + min(fewest[a - coin])")
}

fun minCoins(coins: IntArray, amount: Int): Int {
    if (amount < 0) return -1
    val inf = amount + 1
    val fewest = IntArray(amount + 1) { inf }
    fewest[0] = 0
    for (a in 1..amount) {
        for (c in coins) {
            if (c <= a && fewest[a - c] + 1 < fewest[a]) fewest[a] = fewest[a - c] + 1
        }
    }
    return if (fewest[amount] >= inf) -1 else fewest[amount]
}

fun lcsLength(s: String, t: String): Int {
    TODO("dp[i][j] for the first i letters of s and first j of t")
}

fun lcsLength(s: String, t: String): Int {
    val dp = Array(s.length + 1) { IntArray(t.length + 1) }
    for (i in 1..s.length) for (j in 1..t.length) {
        dp[i][j] = if (s[i - 1] == t[j - 1]) dp[i - 1][j - 1] + 1
                   else maxOf(dp[i - 1][j], dp[i][j - 1])
    }
    return dp[s.length][t.length]
}

12. Takeaways

• Write the base case first, and make sure each call moves toward it.
• Recursion uses call stack space; very deep recursion should become a loop.
• Backtracking: choose, explore, un-choose, and save a copy of each answer.
• Greedy is fast but must be justified; test it against a slow, correct solution.
• For DP, write the meaning of the state in one sentence before any code.
• If a recursion repeats the same arguments, add a cache. If only the last row or two values are needed, drop the full table.
• Next up: Part 8 collects the reusable programming patterns, such as two pointers and sliding windows.