Dynamic Programming Practice: From 1D to 2D

You have learned the method. Now comes the part that makes it stick: using it on problem after problem until the steps feel natural.

This article works through four classic problems, from a one-dimensional table to a two-dimensional one. For every one, we go through the same six questions: state, transition, base cases, evaluation order, answer, cost, and we also say why the answer is right, because a transition you cannot justify is a guess. The exercises add three more problems, including a knapsack.

• How to apply the six-step workflow to new problems.
• A useful trick for finding a transition: ask what the last decision was.
• 1D DP with O(1) space (climbing stairs, house robber).
• 2D DP on a grid (unique paths with obstacles), and on two sequences (longest common subsequence).
• How to rebuild the actual solution, not only its value.

Problem. You climb a staircase of n steps, taking either 1 or 2 steps at a time. In how many distinct ways can you reach the top? For n = 4 there are 5 ways: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2.

1. State. ways[i] = the number of distinct ways to reach step i (counting the ground as step 0).
2. Transition. Ask: what was the last move? Either a 1-step from i - 1, or a 2-step from i - 2. These two groups are disjoint (different last moves) and together cover everything. So ways[i] = ways[i - 1] + ways[i - 2].
3. Base cases. ways[0] = 1 (one way to stand on the ground: do nothing) and ways[1] = 1.
4. Order. Increasing i.
5. Answer. ways[n].
6. Cost. n states, constant work each: O(n) time. Each state needs only the previous two, so O(1) space.

This is the Fibonacci recurrence in disguise. The numbers grow fast: they exceed the range of int at n = 46, so we use long.

Variation: if you may take 1, 2 or 3 steps, the last move can be any of three, so ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3]. The method is the same.

Problem. A street has houses with amounts of money a[0], a[1], ..., a[n - 1]. You cannot rob two adjacent houses. Find the maximum you can rob. For [2, 7, 9, 3, 1] the answer is 12 (houses with 2, 9 and 1).

1. State. best[i] = the maximum money from the first i houses (positions 0 to i - 1).
2. Transition. Ask about the last house considered, house i - 1. Either you skip it, and the best is best[i - 1]. Or you rob it, and since the previous house is off limits, you add a[i - 1] to best[i - 2]. Take the larger: best[i] = max(best[i - 1], best[i - 2] + a[i - 1]).
3. Base cases. best[0] = 0 (no houses), best[1] = a[0].
4. Order. Increasing i.
5. Answer. best[n].
6. Cost. O(n) time, and O(1) space with two variables.

Why it is correct. Every strategy either robs the last house or it does not, and those cases do not overlap. Among strategies that skip it, the best is best[i - 1] by definition. Among those that rob it, the other houses must come from the first i - 2 houses, and the best of those is best[i - 2]. We have taken the best of both groups, so no better strategy exists. (This assumes the amounts are non-negative.)

Dry run for [2, 7, 9, 3, 1]:

The answer is 12.

// File: Main.javapublic class Main {    // Number of ways to climb n steps taking 1 or 2 at a time.    static long climbStairs(int n) {        long twoBack = 1;               // ways[0]        long oneBack = 1;               // ways[1]        for (int i = 2; i <= n; i++) {            long current = oneBack + twoBack;            twoBack = oneBack;            oneBack = current;        }        return n == 0 ? 1 : oneBack;    }    // Variation: steps of 1, 2 or 3.    static long climbStairsUpToThree(int n) {        long[] ways = new long[Math.max(n + 1, 3)];        ways[0] = 1;        ways[1] = 1;        ways[2] = 2;        for (int i = 3; i <= n; i++) {            ways[i] = ways[i - 1] + ways[i - 2] + ways[i - 3];        }        return ways[n];    }    static long houseRobber(int[] a) {        long twoBack = 0;               // best for the first i - 2 houses        long oneBack = 0;               // best for the first i - 1 houses        for (int money : a) {            long current = Math.max(oneBack, twoBack + money);            twoBack = oneBack;            oneBack = current;        }        return oneBack;    }    public static void main(String[] args) {        System.out.println(climbStairs(0) + " " + climbStairs(1) + " " + climbStairs(2) + " " + climbStairs(4) + " " + climbStairs(10));        System.out.println(climbStairs(50) + " " + climbStairsUpToThree(4) + " " + climbStairsUpToThree(10));        System.out.println(houseRobber(new int[] {2, 7, 9, 3, 1}) + " " + houseRobber(new int[] {1, 2, 3, 1}) + " " + houseRobber(new int[] {2, 1, 1, 2}));        System.out.println(houseRobber(new int[] {}) + " " + houseRobber(new int[] {5}) + " " + houseRobber(new int[] {5, 1}) + " " + houseRobber(new int[] {5, 1, 1, 5}));    }}

1 1 2 5 8920365011074 7 27412 4 40 5 5 10

Notice how the code uses the base cases: the loop in houseRobber starts with both "previous" values at 0, so an empty street gives 0, a single house gives its value, and no special case is needed.

Problem. A robot is in the top-left cell of an m × n grid and may only move right or down. How many distinct paths lead to the bottom-right cell? Some cells may be obstacles that cannot be entered.

1. State. paths[r][c] = the number of ways to reach cell (r, c) from (0, 0).
2. Transition. The last move into (r, c) came from above (r - 1, c) or from the left (r, c - 1). So paths[r][c] = paths[r - 1][c] + paths[r][c - 1]. If (r, c) is an obstacle, paths[r][c] = 0.
3. Base cases. The start has one way, paths[0][0] = 1 (if it is not an obstacle). Cells in the first row and first column are reachable only from one direction, which our formula handles if we treat out-of-grid neighbours as 0.
4. Order. Row by row, left to right. Each cell's inputs (above and left) are computed before it.
5. Answer. paths[m - 1][n - 1].
6. Cost. m × n states, constant work each: O(m × n) time. A row only needs the row above it, so we can keep one row and update it in place: O(n) space.

Dry run on a 3 × 4 grid with no obstacles:

For example paths[2][2] = paths[1][2] + paths[2][1] = 3 + 3 = 6. The answer is 10. (It also equals the number of ways to choose which 2 of the 5 moves are "down": C(5, 2) = 10.)

With the one-row version, row[c] holds the paths to the cell in the current row. When we process a cell, row[c] still holds the value from the row above (the "from above" part), and row[c - 1] has just been updated for this row (the "from left" part). So the update is simply row[c] += row[c - 1].

// File: Main.javapublic class Main {    // grid[r][c] == 1 means an obstacle. Counts paths moving only right or down.    static long uniquePaths(int[][] grid) {        int rows = grid.length;        if (rows == 0 || grid[0].length == 0) {            return 0;        }        int cols = grid[0].length;        long[] row = new long[cols];                      // paths to each cell of the current row        row[0] = grid[0][0] == 1 ? 0 : 1;        for (int r = 0; r < rows; r++) {            for (int c = 0; c < cols; c++) {                if (grid[r][c] == 1) {                    row[c] = 0;                           // an obstacle: no path goes through it                } else if (c > 0) {                    row[c] += row[c - 1];                 // from above (already in row[c]) plus from the left                }            }        }        return row[cols - 1];    }    static long uniquePathsEmpty(int m, int n) {        return uniquePaths(new int[m][n]);    }    public static void main(String[] args) {        System.out.println(uniquePathsEmpty(3, 4) + " " + uniquePathsEmpty(3, 7) + " " + uniquePathsEmpty(1, 1) + " " + uniquePathsEmpty(1, 5) + " " + uniquePathsEmpty(18, 18));        int[][] withObstacle = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};        System.out.println(uniquePaths(withObstacle));        System.out.println(uniquePaths(new int[][] {{1, 0}, {0, 0}}) + " " + uniquePaths(new int[][] {{0, 0}, {0, 1}}) + " " + uniquePaths(new int[][] {{0, 1}}) + " " + uniquePaths(new int[0][]));    }}

10 28 1 1 233360622020 0 0 0

The 3 × 3 grid with an obstacle in the middle has 2 paths (around the obstacle either way). A blocked start or a blocked end means zero paths. The 18 × 18 result needs long (it is C(34, 17), about 2.3 billion, which is already past the int range).

Problem. Given two strings, find the length of their longest common subsequence (LCS): the longest sequence of characters that appears in both strings in the same order, but not necessarily contiguously. For "ACBD" and "ABCD" it is 3 ("ACD" or "ABD"). This problem is behind tools like diff and DNA comparison.

1. State. dp[i][j] = the LCS length of the first i characters of a and the first j characters of b.

2. Transition. Look at the last characters, a[i - 1] and b[j - 1].

   • If they are equal, that character can end a common subsequence, so dp[i][j] = dp[i - 1][j - 1] + 1.
   • If they differ, at least one of them is not used, so the best is the better of dropping the last character of a or of b: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
3. Base cases. dp[0][j] = 0 and dp[i][0] = 0: an empty string has nothing in common with anything.
4. Order. Row by row, left to right. Each cell reads from the cell above, the cell to the left, and the diagonal one: all earlier.
5. Answer. dp[m][n].
6. Cost. (m + 1) × (n + 1) states, constant work each: O(m × n) time and O(m × n) space. If you only need the length, two rows suffice (O(min(m, n)) space), but then you cannot rebuild the subsequence.

Why matching characters can be taken greedily. If the last characters are equal, some optimal common subsequence ends with that character. Any optimal solution that does not use one of those two characters can be changed to use it without losing length, so including the match is never a mistake.

Dry run for a = "ACBD" (rows) and b = "ABCD" (columns):

Take the cell for row C, column C: the characters match, so it is dp[A][B] + 1 = 1 + 1 = 2. Take row B, column C: they differ, so it is max(dp[C][C], dp[B][B]) = max(2, 2) = 2. The answer, bottom-right, is 3.

To recover an actual LCS, walk backwards from (m, n):

• if a[i - 1] == b[j - 1], this character is part of the answer: record it and move diagonally to (i - 1, j - 1);
• otherwise, move to the neighbour with the larger value: up (i - 1, j) or left (i, j - 1). (Either is fine when they tie.)

The characters come out in reverse, so reverse the result at the end. Following this on the table above: D = D (take D), then at (B, C) the cells above and to the left tie, we go up to (C, C) where C = C (take C), then at (A, B) we go left to (A, A) where A = A (take A). The result is "ACD".

// File: Main.javapublic class Main {    static int[][] lcsTable(String a, String b) {        int m = a.length();        int n = b.length();        int[][] dp = new int[m + 1][n + 1];                // row 0 and column 0 stay 0        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (a.charAt(i - 1) == b.charAt(j - 1)) {                    dp[i][j] = dp[i - 1][j - 1] + 1;                } else {                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);                }            }        }        return dp;    }    static String lcs(String a, String b) {        int[][] dp = lcsTable(a, b);        StringBuilder result = new StringBuilder();        int i = a.length();        int j = b.length();        while (i > 0 && j > 0) {            if (a.charAt(i - 1) == b.charAt(j - 1)) {                result.append(a.charAt(i - 1));            // part of the answer                i--;                j--;            } else if (dp[i - 1][j] >= dp[i][j - 1]) {                i--;                                       // the better answer came from above            } else {                j--;                                       // it came from the left            }        }        return result.reverse().toString();    }    public static void main(String[] args) {        int[][] table = lcsTable("ACBD", "ABCD");        for (int[] row : table) {            StringBuilder line = new StringBuilder();            for (int v : row) {                line.append(v).append(' ');            }            System.out.println(line.toString().trim());        }        String[][] tests = {{"ACBD", "ABCD"}, {"abcde", "ace"}, {"abc", "abc"}, {"abc", "def"}, {"", "abc"}, {"AGGTAB", "GXTXAYB"}};        for (String[] t : tests) {            String sequence = lcs(t[0], t[1]);            System.out.println("[" + t[0] + "] [" + t[1] + "] -> " + sequence.length() + " \"" + sequence + "\"");        }    }}

0 0 0 0 00 1 1 1 10 1 1 2 20 1 2 2 20 1 2 2 3[ACBD] [ABCD] -> 3 "ACD"[abcde] [ace] -> 3 "ace"[abc] [abc] -> 3 "abc"[abc] [def] -> 0 ""[] [abc] -> 0 ""[AGGTAB] [GXTXAYB] -> 4 "GTAB"

The tests include a few edge cases: identical strings (the LCS is the whole string), nothing in common (length 0) and an empty string. An LCS may not be unique ("ACBD" and "ABCD" also have "ABD"), and the walk-back rule decides which one you get.

When you cannot see the transition, ask: what is the last thing that happened (or the last decision made) in a solution to the problem? List the possible answers. Each possibility leads to a smaller subproblem.

The next piece of advice is to say the state in words: "the best I can do using the first i items", "the number of ways to reach (r, c)". If the sentence is clear, the rest follows.

• Empty input. An empty street, an empty string, or a 0 × 0 grid. Decide the answer and check the code.
• Blocked start or end in grid problems.
• Off-by-one between the table and the input. dp[i] often refers to the first i items, which are a[0..i - 1]. Keep the mapping in a comment.
• int overflow in counting problems. Path and stair counts grow fast. Use long, or the modulus the problem specifies.
• Wrong evaluation order, for example reading row[c - 1] before it has been updated for the current row.
• Forgetting that a 1D space optimisation changes what the array means. After optimising, row[c] is either the old row's value or the new row's value, depending on the moment you read it.
• A transition that does not partition the cases. In house robber, Math.max(dp[i-1], dp[i-2]) + a[i] wrongly forces you to rob house i. The transition must take the maximum of the whole alternatives.
• Not testing tiny inputs such as n = 0 and n = 1.
• Starting a table from 1 and indexing -1. Make base cases explicit, or add a padding row and column of zeros.

static int robBuggy(int[] a) {    int[] dp = new int[a.length];    dp[0] = a[0];    dp[1] = Math.max(a[0], a[1]);    for (int i = 2; i < a.length; i++) {        dp[i] = Math.max(dp[i - 1], dp[i - 2]) + a[i];    }    return dp[a.length - 1];}

// File: Main.javaimport java.util.Arrays;public class Main {    static int[] robTable(int[] a) {        int[] best = new int[a.length + 1];        if (a.length >= 1) {            best[1] = a[0];        }        for (int i = 2; i <= a.length; i++) {            best[i] = Math.max(best[i - 1], best[i - 2] + a[i - 1]);        }        return best;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(robTable(new int[] {1, 2, 3, 1})));        System.out.println(Arrays.toString(robTable(new int[] {2, 1, 1, 2})));    }}

[0, 1, 2, 4, 4][0, 2, 2, 3, 4]

// File: Main.javapublic class Main {    static long minPathSum(int[][] grid) {        if (grid.length == 0 || grid[0].length == 0) {            return 0;        }        int rows = grid.length;        int cols = grid[0].length;        long[] row = new long[cols];                  // best cost to each cell of the current row        for (int r = 0; r < rows; r++) {            for (int c = 0; c < cols; c++) {                if (r == 0 && c == 0) {                    row[c] = grid[0][0];                } else if (r == 0) {                    row[c] = row[c - 1] + grid[r][c];             // only from the left                } else if (c == 0) {                    row[c] = row[c] + grid[r][c];                 // only from above (the old row[c])                } else {                    row[c] = Math.min(row[c], row[c - 1]) + grid[r][c];                }            }        }        return row[cols - 1];    }    public static void main(String[] args) {        System.out.println(minPathSum(new int[][] {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));        System.out.println(minPathSum(new int[][] {{1, 2, 3}, {4, 5, 6}}));        System.out.println(minPathSum(new int[][] {{7}}));        System.out.println(minPathSum(new int[][] {}));    }}

71270

// File: Main.javapublic class Main {    static long decodeWays(String s) {        int n = s.length();        if (n == 0) {            return 0;        }        long twoBack = 1;                       // ways[i - 2], starting with ways[0] = 1        long oneBack = s.charAt(0) == '0' ? 0 : 1;   // ways[1]        for (int i = 2; i <= n; i++) {            long current = 0;            if (s.charAt(i - 1) != '0') {                current += oneBack;             // decode the last digit on its own            }            int pair = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');            if (pair >= 10 && pair <= 26) {                current += twoBack;             // decode the last two digits together            }            twoBack = oneBack;            oneBack = current;        }        return oneBack;    }    public static void main(String[] args) {        System.out.println(decodeWays("226") + " " + decodeWays("12") + " " + decodeWays("06") + " " + decodeWays("10") + " " + decodeWays("100"));        System.out.println(decodeWays("0") + " " + decodeWays("27") + " " + decodeWays("") + " " + decodeWays("1111111111"));    }}

3 2 0 1 00 1 0 89

// File: Main.javapublic class Main {    static int robBuggy(int[] a) {        int[] dp = new int[a.length];        dp[0] = a[0];        dp[1] = Math.max(a[0], a[1]);        for (int i = 2; i < a.length; i++) {            dp[i] = Math.max(dp[i - 1], dp[i - 2]) + a[i];        }        return dp[a.length - 1];    }    static int robFixed(int[] a) {        if (a.length == 0) {            return 0;        }        if (a.length == 1) {            return a[0];        }        int[] dp = new int[a.length];        dp[0] = a[0];        dp[1] = Math.max(a[0], a[1]);        for (int i = 2; i < a.length; i++) {            dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i]);        }        return dp[a.length - 1];    }    public static void main(String[] args) {        System.out.println(robBuggy(new int[] {5, 1, 1, 5}) + " " + robFixed(new int[] {5, 1, 1, 5}));        try {            robBuggy(new int[] {5});        } catch (ArrayIndexOutOfBoundsException e) {            System.out.println("buggy version crashes for a single house; fixed gives " + robFixed(new int[] {5}));        }    }}

11 10buggy version crashes for a single house; fixed gives 5

// File: Main.javapublic class Main {    static long knapsack(int[] weights, int[] values, int capacity) {        long[] dp = new long[capacity + 1];                    // dp[w] = best value with capacity w        for (int i = 0; i < weights.length; i++) {            for (int w = capacity; w >= weights[i]; w--) {      // downward: each item at most once                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);            }        }        return dp[capacity];    }    static long unboundedKnapsack(int[] weights, int[] values, int capacity) {        long[] dp = new long[capacity + 1];        for (int i = 0; i < weights.length; i++) {            for (int w = weights[i]; w <= capacity; w++) {      // upward: an item may repeat                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);            }        }        return dp[capacity];    }    public static void main(String[] args) {        int[] weights = {1, 3, 4, 5};        int[] values = {1, 4, 5, 7};        System.out.println(knapsack(weights, values, 7) + " " + unboundedKnapsack(weights, values, 7));        System.out.println(knapsack(weights, values, 10) + " " + unboundedKnapsack(weights, values, 10));        System.out.println(knapsack(weights, values, 0) + " " + knapsack(new int[] {}, new int[] {}, 10) + " " + knapsack(new int[] {10}, new int[] {5}, 4));    }}

9 913 140 0 0

• Next: Tries and Prefix-Based Search moves to a specialised tree for strings.
• Revisit: Dynamic Programming: Learn to Recognize Overlapping Subproblems whenever a new problem feels unfamiliar. Re-run the six steps, and check that your state sentence is precise.
• Where to practise more: the study plan in Your 12-Week DSA Study and Revision Plan schedules DP across two weeks, with spaced revision of the examples here.