Step 4 of 6

Bottom-up DP: filling a table

Memoization works top-down: start from the big question and recurse. The other way is bottom-up (also called tabulation): fill a table starting from the smallest subproblems, so that every entry you compute only needs entries you've already filled. No recursion at all, which means no stack depth limit, and a Vec index is cheaper than hashing a key.

fn fib(n: usize) -> u64 {
    let mut table = vec![0u64; n + 1];
    if n >= 1 {
        table[1] = 1;
    }
    for i in 2..=n {
        table[i] = table[i - 1] + table[i - 2];
    }
    table[n]
}

fn min_cost(cost: &[u32]) -> u32 {
    // best[i] = the cheapest way to stand on step i; the top is step cost.len().
    // You may start on step 0 or 1 for free; leaving step j costs cost[j].
    let n = cost.len();
    let mut best = vec![0; n + 1];
    for i in 2..=n {
        best[i] = (best[i - 1] + cost[i - 1]).min(best[i - 2] + cost[i - 2]);
    }
    best[n]
}

fn main() {
    println!("fib(90) = {}", fib(90));
    println!("{}", min_cost(&[10, 15, 20]));
    println!("{}", min_cost(&[1, 100, 1, 1, 1, 100, 1, 1, 100, 1]));
}

fib(90) = 2880067194370816120
15
6

A recipe for DP problems

1. State: say in words what one table entry means. "best[i] is the cheapest cost to stand on step i."
2. Recurrence: how an entry is built from smaller ones. "best[i] is the cheaper of arriving from step i-1 or from step i-2."
3. Base cases: the entries you know without computing. "best[0] = best[1] = 0."
4. Order: fill the table so dependencies are ready (here: increasing i).
5. Answer: which entry holds it ("best[n]").

Writing the state down in a comment, as above, is the single most useful habit for DP.

Saving memory

When an entry only depends on the last few entries, you don't need the whole table. Fibonacci only needs the previous two values:

let (mut a, mut b) = (0u64, 1u64);
for _ in 0..n {
    (a, b) = (b, a + b); // destructuring assignment: both update at once
}
// a is now fib(n)

Common mistakes

• A table one too short. If the answer is table[n], the table needs n + 1 entries.
• Filling in the wrong order, reading an entry that's still the initial 0.
• "Impossible" values. For a minimum, initialize entries to a marker like u32::MAX (or use Option<u32>), and never add 1 to the marker: u32::MAX + 1 overflows.
• Trusting greed. For coins [1, 3, 4] and amount 6, "always take the biggest coin" gives 4 + 1 + 1 (three coins), but 3 + 3 is two. DP checks every option.

Your task

The classic coin change. Write fn min_coins(coins: &[u32], amount: u32) -> Option<u32>: the fewest coins (each coin value can be used any number of times) that add up to exactly amount, or None if it's impossible. Make amount 0 need 0 coins. State: best[a] is the fewest coins for amount a; for each coin c <= a, best[a] could be best[a - c] + 1. The tests include amounts up to 100,000.

Challenge 2

The vending machine team wants to know in how many different ways an amount can be paid (order doesn't matter: 1 + 2 and 2 + 1 are the same way). Write fn ways_to_pay(coins: &[u32], amount: u32) -> u64. There's 1 way to pay 0.

State: ways[a] = number of ways to pay a with the coins considered so far. Loop over the coins on the outside and the amounts on the inside: ways[a] += ways[a - coin]. (With the amounts outside you'd count 1 + 2 and 2 + 1 separately.) The tests include paying 10,000 with eight coin values.

Challenge 3

A delivery drone flies along a street where each house offers a tip, but noise rules forbid stopping at two neighboring houses on the same run. Write fn max_tips(tips: &[u32]) -> u64: the largest total it can collect.

State: the best total using the houses up to i. At house i you either skip it (keep the best up to i - 1) or take it (its tip plus the best up to i - 2). You only ever need the last two values, so use two variables instead of a table. The tests include a street of 200,000 houses.

Previous: Memoization with a HashMap Next: Two-dimensional DP: grids and strings