Dynamic programming in Rust

Your teacher sets a long sum: 23 × 47. Halfway through, you need 23 × 40, and you work it out. A few lines later, the same 23 × 40 turns up again. Do you work it out again? Of course not. You wrote the answer in the margin, so you just look at it.

That is the whole idea of dynamic programming, often shortened to DP. The name sounds grander than it is. It means: when a problem breaks into smaller problems, and the same small problems keep coming up, solve each small problem once, write the answer down, and look it up next time.

The trouble it fixes is real. Plain recursion (lesson 16) can solve the same small problem thousands of times. The first example below does 21,891 calls to count the ways to climb just 20 stairs. With a margin to write in, it does about 20.

Reach for DP when a question asks for the best, the fewest, the most, or how many ways, and the choices at each step feed into the next. Interviewers love it, because the idea is simple and the first attempt is easy to get wrong.

Start with an example before the rule. You are climbing a staircase of 5 stairs, and each time you may step up 1 stair or 2. How many different ways are there to reach the top?

Think about the very last step. You arrived either from stair 4 (with a 1-step) or from stair 3 (with a 2-step). So the ways to reach stair 5 are the ways to reach stair 4, plus the ways to reach stair 3. In general, ways(n) = ways(n - 1) + ways(n - 2).

That one sentence is the recurrence: the answer to a big problem, written in terms of smaller ones. Add the base cases, the tiny problems you answer directly: one way to stand at the bottom, one way to reach stair 1.

Now the trouble. To work out ways(5), a plain recursion asks for ways(4) and ways(3). And ways(4) asks for ways(3) again, and ways(2). The same questions keep appearing. This is called overlapping subproblems, and it is the sign that DP will help. With 20 stairs, ways(2) alone is asked thousands of times.

There are two ways to stop the waste, and they give the same answers.

Top-down, with a memo. Keep the recursion exactly as it is. But before doing any work, look in a notebook, called a memo. If the answer is there, return it. If not, work it out, and write it in the notebook before returning. Each question is now answered once.

Bottom-up, with a table. Skip the recursion. Make a table with one slot for each small problem, and fill it from the smallest upward. Slot 0 and slot 1 hold the base cases. Slot 2 is slot 1 plus slot 0. Slot 3 is slot 2 plus slot 1. By the time you reach the slot you want, everything it needs is already filled in.

The picture shows a table for a different problem, coin change. With coins worth 1, 3 and 4, what is the fewest coins that make 6? Each slot holds the answer for that amount. To fill slot 6, try every coin: step back by the coin's value, and add one coin to the answer already in that slot. Coin 3 steps back to slot 3, which holds 1, so that is 2 coins. That is the best, and it beats the cashier who greedily grabs the biggest coin first.

How do you find a DP solution? Ask four questions.

1. What is a small problem? For stairs, "ways to reach stair i". The answer to this is the state.
2. How does a small problem follow from smaller ones? That is the recurrence.
3. What are the base cases? The smallest problems you can answer on sight.
4. What order fills the table? Smallest first, so everything needed is ready.

Remember: if the same small question keeps coming back, write its answer down the first time.

First, the slow version, with a counter to show the waste.

/// How many ways to climb `n` stairs, taking 1 or 2 steps at a time? The last
/// step was either a 1 (from stair n-1) or a 2 (from stair n-2). `calls`
/// counts how often the function ran, to show the waste.
pub fn climb_slow(n: u32, calls: &mut u64) -> u64 {
    *calls += 1;
    if n <= 1 {
        return 1; // one way to stand still, one way to climb one stair
    }
    climb_slow(n - 1, calls) + climb_slow(n - 2, calls)
}

The recurrence is the last line. calls is only here to count, so you can see the cost.

let mut calls = 0;
let ways = climb_slow(20, &mut calls);

println!("{} ways, {} calls", ways, calls);
assert_eq!(ways, 10946);
assert_eq!(calls, 21891); // to count 20 stairs, it ran over twenty thousand times

Twenty stairs: 10,946 ways, but the function ran 21,891 times. Add a few more stairs and it takes forever. Now the memo.

/// The same idea, but every answer is written down the first time it is found.
pub fn climb_memo(n: usize) -> u64 {
    let mut memo: Vec<Option<u64>> = vec![None; n + 1];
    ways(n, &mut memo)
}

fn ways(n: usize, memo: &mut [Option<u64>]) -> u64 {
    if n <= 1 {
        return 1;
    }
    if let Some(known) = memo[n] {
        return known; // solved before, so no new work
    }
    let answer = ways(n - 1, memo) + ways(n - 2, memo);
    memo[n] = Some(answer);
    answer
}

memo is a Vec with one slot per stair, holding an Option<u64>. None means "not worked out yet". The function checks the slot first: if let Some(known) = memo[n] returns the saved answer straight away. Otherwise it recurses, saves the result with memo[n] = Some(answer), and returns it. The recursion is unchanged. It only has a notebook now.

And the table, bottom-up.

/// The same answer with no recursion: fill a table from the smallest stairs up.
pub fn climb_table(n: usize) -> u64 {
    // table[i] is the number of ways to reach stair i.
    let mut table = vec![1; n + 1]; // stairs 0 and 1 have one way each
    for i in 2..=n {
        table[i] = table[i - 1] + table[i - 2];
    }
    table[n]
}

No recursion at all. The table starts as all 1s, which covers the two base cases. Then a loop fills slot 2, slot 3, and on up to n. This one is shorter and cannot overflow the call stack. Fifty stairs take fifty small steps.

println!("{}", climb_table(20));
assert_eq!(climb_table(20), 10946);
assert_eq!(climb_table(50), 20_365_011_074); // the slow way would never finish

Which should you use? Both cost the same. The memo is closest to the thinking, and only computes what is needed. The table is usually a little faster, and avoids deep recursion. Many people write the memo first to get the idea right, and then convert to a table.

Remember: a memo is a recursion with a notebook. A table is the same notebook, filled in order.

Now coin change, the problem from the picture.

/// The fewest coins that add up to `amount`, or `None` if they cannot.
pub fn min_coins(coins: &[usize], amount: usize) -> Option<usize> {
    // best[a] is the fewest coins for amount a. `None` means "cannot be made".
    let mut best: Vec<Option<usize>> = vec![None; amount + 1];
    best[0] = Some(0); // zero rupees needs zero coins

    for a in 1..=amount {
        for &coin in coins {
            if coin > a {
                continue;
            }
            // Use one coin, then make what is left over the cheapest way.
            if let Some(rest) = best[a - coin] {
                let candidate = rest + 1;
                if best[a].is_none_or(|current| candidate < current) {
                    best[a] = Some(candidate);
                }
            }
        }
    }
    best[amount]
}

Go through it in order.

• best[a] is the fewest coins for amount a. None means that amount cannot be made, and it stays None if no coin works.
• best[0] = Some(0): zero rupees needs zero coins. That is the base case everything builds on.
• For each amount, try every coin. A coin bigger than the amount is skipped. Otherwise, look up the answer for what is left, best[a - coin]. If that was possible, using this coin costs one more.
• Keep the smallest candidate. The answer is the last slot.

Last, a classic on text. A subsequence is some letters of a text, in the same order, but not necessarily side by side: "ace" is a subsequence of "abcde". The longest common subsequence (LCS) of two texts is the longest one they share. Tools that show the difference between two files lean on this idea.

/// The length of the longest common subsequence of two texts: letters that
/// appear in both, in the same order, but not necessarily side by side.
pub fn lcs_length(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();

    // table[i][j] answers the question for the first i letters of `a` and the
    // first j letters of `b`. Row 0 and column 0 are the empty texts: all zero.
    let mut table = vec![vec![0; b.len() + 1]; a.len() + 1];

    for i in 1..=a.len() {
        for j in 1..=b.len() {
            table[i][j] = if a[i - 1] == b[j - 1] {
                table[i - 1][j - 1] + 1 // the letters match, so extend the best so far
            } else {
                table[i - 1][j].max(table[i][j - 1]) // skip a letter from either text
            };
        }
    }
    table[a.len()][b.len()]
}

The table has a row for each prefix of the first text, and a column for each prefix of the second. table[i][j] is the answer for the first i letters of one and the first j of the other. Row 0 and column 0 are the empty texts, so they are all zero. Then each slot has two cases. If the last letters match, they both belong in the common subsequence, so the answer is the diagonal slot plus 1. If they do not match, one of them is left out, so take the better of the slot above and the slot to the left.

Remember: a table slot is the answer to a smaller question, and each slot is built from slots that are already filled.

Rust has no "DP" feature, and it does not need one. The tools are the ones from earlier lessons.

• A Vec is the table when the small problems are numbered 0, 1, 2, and so on. A Vec<Vec<_>> is a table with rows and columns, as in the LCS.
• A HashMap is the memo when the small problems are not neat numbers. The key could be a pair of numbers, a word, or anything you can hash.
• Option marks "not worked out yet", or "cannot be done", far more safely than a made-up number such as -1 or a huge value.
• max and min on numbers, and iter().max() on a list, pick the best candidate.

Here is the same memo idea with a HashMap, for the Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, and so on, each the sum of the two before it). The Playground link runs it.

use std::collections::HashMap;

/// The n-th Fibonacci number: 0, 1, 1, 2, 3, 5, 8, ...
fn fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n <= 1 {
        return n;
    }
    if let Some(&known) = memo.get(&n) {
        return known;
    }
    let answer = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, answer);
    answer
}

let mut memo = HashMap::new();
println!("{}", fib(80, &mut memo));
assert_eq!(fib(80, &mut memo), 23_416_728_348_467_685);

memo.get(&n) looks up the notebook, and memo.insert writes in it. The helper fib is nested inside the function that uses it, which is a tidy way to keep it close. The memo is passed in as &mut, so every call shares the same notebook.

One honest warning. DP answers can grow fast, and a u64 runs out of room. Fibonacci number 93 is the last that fits. For bigger results, a method like checked_add gives back None instead of overflowing, so you find out rather than get a wrong number.

The general rule: the time is about the number of table slots times the work per slot. Often you can keep fewer rows than the whole table if each row only needs the one before it, which saves space.

For each one, ask the four questions from the lesson: the state, the recurrence, the base case and the order. Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn max_loot(houses: &[u32]) -> u32 {
    todo!("for each house: rob it, or skip it")
}

/// Houses in a row each hold some money. Two houses side by side set off
/// the alarm, so you cannot rob neighbours. The most you can take.
pub fn max_loot(houses: &[u32]) -> u32 {
    // Only the last two answers matter, so two variables are the whole table.
    // `one_back` is the best so far, and `two_back` the best before that.
    let (mut two_back, mut one_back) = (0, 0);
    for &money in houses {
        // Rob this house on top of the best from two houses back...
        let robbed = two_back + money;
        two_back = one_back;
        // ...or skip it, and keep the best so far.
        one_back = one_back.max(robbed);
    }
    one_back
}

pub fn min_path_sum(grid: &[Vec<u32>]) -> u32 {
    todo!("you can only arrive from above or from the left")
}

/// A grid of costs. Walk from the top-left to the bottom-right, moving only
/// right or down. The smallest total of the cells you step on.
pub fn min_path_sum(grid: &[Vec<u32>]) -> u32 {
    if grid.is_empty() || grid[0].is_empty() {
        return 0;
    }
    let (rows, cols) = (grid.len(), grid[0].len());

    // cost[r][c] is the cheapest way to arrive at cell (r, c).
    let mut cost = vec![vec![0; cols]; rows];
    for r in 0..rows {
        for c in 0..cols {
            let arrive = match (r, c) {
                (0, 0) => 0,
                (0, _) => cost[r][c - 1], // top row: only from the left
                (_, 0) => cost[r - 1][c], // left column: only from above
                _ => cost[r - 1][c].min(cost[r][c - 1]), // the cheaper of the two
            };
            cost[r][c] = arrive + grid[r][c];
        }
    }
    cost[rows - 1][cols - 1]
}

pub fn longest_increasing(nums: &[i32]) -> usize {
    todo!("the longest chain that ends at each item")
}

/// The length of the longest run of items, not necessarily side by side,
/// that keep getting bigger.
pub fn longest_increasing(nums: &[i32]) -> usize {
    // chain[i] is the longest increasing chain that ENDS at item i.
    let mut chain = vec![1; nums.len()];
    for i in 0..nums.len() {
        for j in 0..i {
            if nums[j] < nums[i] {
                chain[i] = chain[i].max(chain[j] + 1);
            }
        }
    }
    chain.into_iter().max().unwrap_or(0)
}

Dynamic programming is the topic people fear most, and it is mostly a habit of mind. Learn the steps, and it turns into routine.

• Spot the signals. "Fewest", "most", "longest", "number of ways", "can it be made", and a choice at every step all point to DP. A recursion that repeats its own calls is a strong hint.
• Say the four things. Out loud: the state, the recurrence, the base cases, and the order. An interviewer who hears those four has heard a complete solution.
• Start with the brute force. Write or describe the plain recursion first. Then point at the repeated calls, say "overlapping subproblems", and add the memo. That path is far easier than jumping to a table.
• Choose the state carefully. Most of the work is deciding what the table's index means, like "ends exactly at i". A good state makes the recurrence obvious.
• Know memo against table. Memo: easy to write from the recursion, computes only what is needed, but uses the call stack. Table: no recursion, usually faster, needs the right fill order.
• Trim the space. If each row only needs the previous row, or each slot only the last two, say you can keep just those. It shows you understand what the table is for.
• Greedy is not DP. A greedy choice, like always taking the biggest coin, can fail, as it did for coins 1, 3, 4 and amount 6. Show the small counter-example, and explain why the table does not have that problem.
• State the cost. It is the number of slots times the work per slot. Say it plainly: "n × m slots, constant work each".

Made by VeraStack Labs