Step 5 of 6

Two-dimensional DP: grids and strings

When a subproblem is described by two numbers (a row and a column, a position in each of two strings), the table becomes 2D: a Vec<Vec<T>>, created with vec![vec![0; cols]; rows].

Counting routes through a grid moving only right or down: every cell can be reached from the cell above or the cell to the left, so its count is the sum of theirs. The first row and column have exactly one route each.

fn count_paths(rows: usize, cols: usize) -> u64 {
    // paths[r][c] = number of ways to reach cell (r, c)
    let mut paths = vec![vec![0u64; cols]; rows];
    for r in 0..rows {
        for c in 0..cols {
            paths[r][c] = if r == 0 || c == 0 {
                1
            } else {
                paths[r - 1][c] + paths[r][c - 1]
            };
        }
    }
    paths[rows - 1][cols - 1]
}

fn main() {
    println!("{}", count_paths(3, 3));
    println!("{}", count_paths(3, 7));
    println!("{}", count_paths(18, 18));
}

6
28
2333606220

Filling row by row, left to right, guarantees the cell above and the cell to the left are ready. It's O(rows × cols) time and memory.

Longest common subsequence

A subsequence keeps some characters in their order, possibly skipping others: "RST" is a subsequence of "RUST". The longest common subsequence (LCS) of two texts is at the heart of diff tools and of git's line-by-line comparisons.

State: dp[i][j] = the LCS length of the first i characters of a and the first j characters of b. Row 0 and column 0 are all 0 (an empty text has nothing in common with anything). Then:

• if a[i - 1] == b[j - 1], that character extends the LCS of both shorter prefixes: dp[i][j] = dp[i - 1][j - 1] + 1;
• otherwise drop the last character of one of them, whichever is better: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

For "CAT" and "CUT":

       ""  C  U  T
   ""   0  0  0  0
   C    0  1  1  1
   A    0  1  1  1
   T    0  1  1  2

The answer, 2 ("CT"), is in the bottom-right corner. The table is (len(a) + 1) × (len(b) + 1): O(n·m) time and memory. Note the - 1s: table index i means "the first i characters", so the character itself is at string position i - 1.

Common mistakes

• Indexing a &str. a[i] doesn't compile; collect the characters first: let a: Vec<char> = a.chars().collect();.
• Swapped dimensions. vec![vec![0; cols]; rows] is indexed [row][col]. Mixing them up panics with index out of bounds on non-square tables.
• Memory. A table for two 100,000-character texts has 10 billion cells. When each row only needs the previous row, keep just two rows.

Your task

Write fn lcs_len(a: &str, b: &str) -> usize, the length of the longest common subsequence of two texts (counting characters). The tests include two texts of 2,000 characters each, which plain recursion could never finish.

Challenge 2

A robot crosses a field from the top-left to the bottom-right cell, moving only right or down. Each cell has an energy cost, and the robot pays for every cell it visits, including the first and the last. Write fn min_path_cost(grid: &[Vec<u32>]) -> u32: the cheapest total (0 for an empty grid).

State: cost[r][c] = the cheapest way to reach cell (r, c), which is the cell's own cost plus the cheaper of the cell above and the cell to the left (only one of those exists on the first row and column). The tests include a 300 by 300 field.

Challenge 3

Command-line tools suggest "did you mean status?" when you type stauts. They measure the edit distance (Levenshtein distance): the fewest single-character insertions, deletions and replacements that turn one word into the other. kitten to sitting is 3.

Write fn edit_distance(a: &str, b: &str) -> usize (counting characters). State: d[i][j] = the distance between the first i characters of a and the first j of b. Turning i characters into nothing takes i deletions (d[i][0] = i), and nothing into j characters takes j insertions (d[0][j] = j). Then if a[i - 1] == b[j - 1] it's d[i - 1][j - 1]; otherwise 1 plus the smallest of d[i - 1][j - 1] (replace), d[i - 1][j] (delete) and d[i][j - 1] (insert). The tests compare two 1,500-character texts.

Previous: Bottom-up DP: filling a table Next: The knapsack problem