Rust for Algorithmic Problem-Solving

Dynamic Programming

Dynamic Programming (DP) solves complex optimization and counting problems by breaking them into overlapping subproblems with optimal substructure and storing each subproblem's result in a table so it is computed only once. In Rust, bottom-up iterative tabulation with flat Vec slices and std::mem::swap rolling rows avoids recursion-limit stack overflows and maximizes L1 cache speed.

2D DP Table Space Optimization (`std::mem::swap(&mut prev_row, &mut curr_row)`):

  Full 2D Table (`N x M` memory):         Rolling 2-Row DP (`2 x M` memory!):
  Row 0: [ .  .  .  .  . ]
  Row 1: [ .  .  .  .  . ]                `prev_row`: [ p0, p1, p2, p3, p4 ]
  ...                                                       |   \
  Row i: [ .  .  .  .  . ]                `curr_row`: [ c0, c1, c2, c3, c4 ]
                                          After finishing row: `mem::swap(&mut prev, &mut curr)`!

Comparing Top-Down Memoization and Bottom-Up Tabulation in Rust

Approach Implementation in Rust Pros Cons
Top-Down Memoization Recursive fn solve(state, memo: &mut Vec<Option<u64>>) Only visits reachable states when state space is sparse. Deep recursion can overflow the call stack for $N \ge 10^5$.
Bottom-Up Tabulation Iterative for loops over dp: Vec<u64> Zero recursion overhead, auto-vectorizable, and supports $O(M)$ rolling-row space reduction! Evaluates all states in topological order.

1. Space-Optimized 1D Knapsack DP ($O(N \cdot W)$ Time, $O(W)$ Memory)

In the 0/1 Knapsack problem, iterating capacities backward (for w in (weight..=capacity).rev()) allows updating a single 1D dp vector in place without overwriting values from the previous item row:

/// Solves the 0/1 Knapsack problem in O(N * W) time and O(W) space using a 1D DP array.
pub fn knapsack_01(items: &[(usize, u64)], capacity: usize) -> u64 {
    let mut dp = vec![0u64; capacity + 1];

    for &(weight, value) in items {
        if weight <= capacity {
            // Iterate BACKWARD (`rev()`) so each item is used at most once!
            for w in (weight..=capacity).rev() {
                dp[w] = dp[w].max(dp[w - weight] + value);
            }
        }
    }

    dp[capacity]
}

2. Rolling-Row 2D DP with std::mem::swap (Levenshtein Edit Distance)

When computing a 2D DP table where row i only depends on row i - 1 (such as Longest Common Subsequence or Levenshtein Edit Distance), allocate two 1D vectors prev and curr and swap their pointers at the end of each row in $O(1)$ time with std::mem::swap(&mut prev, &mut curr):

/// Computes the Levenshtein edit distance between `a` and `b` in O(N * M) time
/// and O(min(N, M)) memory using rolling rows and `std::mem::swap`.
pub fn edit_distance(a: &str, b: &str) -> usize {
    let a = a.as_bytes();
    let b = b.as_bytes();

    let mut prev: Vec<usize> = (0..=b.len()).collect();
    let mut curr: Vec<usize> = vec![0; b.len() + 1];

    for (i, &ch_a) in a.iter().enumerate() {
        curr[0] = i + 1;
        for (j, &ch_b) in b.iter().enumerate() {
            let cost = usize::from(ch_a != ch_b);
            curr[j + 1] = (prev[j + 1] + 1)        // Deletion
                .min(curr[j] + 1)                  // Insertion
                .min(prev[j] + cost);              // Substitution / Match
        }
        // Swap `prev` and `curr` in O(1) time without reallocating!
        std::mem::swap(&mut prev, &mut curr);
    }

    prev[b.len()]
}

fn main() {
    // Items: (weight, value)
    let items = [(2, 30), (3, 50), (4, 70), (5, 80)];
    let best_val = knapsack_01(&items, 7);
    assert_eq!(best_val, 120); // weight 3 (50) + weight 4 (70) = 120

    let dist = edit_distance("kitten", "sitting");
    assert_eq!(dist, 3);

    println!("0/1 Knapsack max value (cap=7): {best_val}, Edit distance: {dist}");
}

0/1 Knapsack max value (cap=7): 120, Edit distance: 3