2D DP: Grids, Knapsacks and Words

Paths through a grid

A robot starts top-left and can only move right or down. How many routes reach each cell? Every cell is reached from above or from the left, so ways[r][c] = ways[r-1][c] + ways[r][c-1]:

public class Main {
    public static void main(String[] args) {
        int rows = 4, cols = 5;
        long[][] ways = new long[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == 0 || c == 0) ways[r][c] = 1;          // edges: only one way
                else ways[r][c] = ways[r - 1][c] + ways[r][c - 1];
            }
        }
        for (long[] row : ways) System.out.println(java.util.Arrays.toString(row));
    }
}

Output

[1, 1, 1, 1, 1]
[1, 2, 3, 4, 5]
[1, 3, 6, 10, 15]
[1, 4, 10, 20, 35]

The 0/1 knapsack

A bag holds at most W kg. Each item has a weight and a value, and you take it or leave it. Maximise the value. dp[i][w] = the best value using the first i items with capacity w:

public class Main {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4, 5};
        int[] value = {15, 50, 60, 90};
        int W = 8, n = weight.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];                                   // leave item i
                if (weight[i - 1] <= w) {                                  // or take it
                    dp[i][w] = Math.max(dp[i][w], value[i - 1] + dp[i - 1][w - weight[i - 1]]);
                }
            }
        }
        System.out.println("best value: " + dp[n][W]);
    }
}

Output

best value: 140

Longest common subsequence

A subsequence keeps letters in order but may skip some: “ace” is a subsequence of “abcde”. The longest subsequence two words share measures how similar they are (used by diff tools and DNA research). dp[i][j] = the LCS length of the first i letters of a and the first j of b:

public class Main {
    static int lcs(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;   // letters match
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);                      // drop one letter
            }
        }
        return dp[a.length()][b.length()];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace"));
        System.out.println(lcs("JAVASCRIPT", "JAVA"));
        System.out.println(lcs("dog", "cat"));
    }
}

Output

3
4
0

Common mistake: Mixing up indexes. With an extra row and column of zeros, dp[i][j] is about letters i - 1 and j - 1. That extra row/column is what makes the base cases free.