Dynamic programming basics

Dynamic programming (DP) saves the answers to subproblems that come up again and again. Start with a recursive solution that's correct. Then ask which parts of the history decide the choices left and their value. Those parts are your state.

In House Robber, let best(i) be the largest total from the first i houses with no two neighbors picked. A valid pick either skips the last house, giving best(i − 1), or takes it, giving best(i − 2) + value[i − 1]. These two cases cover every pick, and they don't overlap.

pub fn rob(values: &[i32]) -> i64 {
    assert!(values.iter().all(|&x| x >= 0));
    let (mut two_back, mut one_back) = (0_i64, 0_i64);
    for &value in values {
        let current = one_back.max(two_back + i64::from(value));
        two_back = one_back;
        one_back = current;
    }
    one_back
}

Before each house, one_back is the best total for the houses so far, and two_back is the best without the last one. The update is the recurrence, line for line. It takes O(n) time and O(1) space. Write out the full table before you shrink it to two variables; saving memory too early hides what depends on what.

Every DP explanation should say five things: what a state means, the transitions, the base cases, the order you fill it in, and where the answer is. "Use a 2D array" says none of them.

States you can't reach need a value that can't be mistaken for a real answer. In a minimum-cost DP, starting every state at zero invents free solutions. Use None, or a carefully handled infinity. Don't add costs to an infinity value without thinking about overflow.

Top-down DP with memoization computes only the states you reach, and often reads like the recurrence. Bottom-up DP fills the table in an explicit order and avoids deep recursion. Both need the same state. If the recurrence has a cycle, memoization alone won't solve it; you may need a different formulation or algorithm.

The cost is roughly the number of states times the work per state, plus reading the input and writing the output. With position and budget as the state, there might be O(nB) states. If each tries B choices, that's O(nB²).

Practice: LC 70 Climbing Stairs, LC 198 House Robber, LC 746 Min Cost Climbing Stairs, LC 322 Coin Change, LC 139 Word Break.

Check your understanding: Can two histories with the same state have different choices ahead? If so, the state is missing something. Does each transition lead to a smaller subproblem that's already solved?