Lesson 39Advanced59 minAssessment-backed

1D and 2D DP

Build table-based solutions for sequences, grids, subsequences, and constraint pairs.

What you will be able to do

Distinguish 1D DP from 2D DP by the number of changing state variables.

Use 1D DP for sequence-prefix problems.

Use 2D DP for grids, two strings, or index plus constraint.

Explain table fill order and dependency direction.

Optimize space only after correctness is clear.

The dimension of DP is not about difficulty. It is about how many pieces of information must change to describe a subproblem.

Choosing Dimensions

A 1D state usually answers a prefix or position question. A 2D state usually tracks two positions, a grid coordinate, or one position plus a remaining constraint.

1D and 2D DP state dimensions — State dimensions should come from the information needed, not from habit.

Scenario: Checkout Path Risk

A commerce team models a checkout flow as a grid of decisions and risk scores. The lowest-risk path to each cell depends on the cell above and left. That is 2D DP because row and column both define the subproblem.

Pattern	State	Examples
1D sequence	dp[i]	climb stairs, house robber, min cost climbing
2D grid	dp[r][c]	unique paths, min path sum
Two strings	dp[i][j]	LCS, edit distance
Index + constraint	dp[i][budget]	knapsack, target sum variants

Grid DP path dependencies — Grid DP fill order follows dependency direction.

Same Pattern in Java, Python, and JavaScript

Minimum path sum is a clean 2D DP: each cell depends on the cheaper of top or left.

class MinPathSum {
    static int minPathSum(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == 0 && c == 0) dp[r][c] = grid[r][c];
                else {
                    int up = r > 0 ? dp[r - 1][c] : Integer.MAX_VALUE / 2;
                    int left = c > 0 ? dp[r][c - 1] : Integer.MAX_VALUE / 2;
                    dp[r][c] = grid[r][c] + Math.min(up, left);
                }
            }
        }
        return dp[rows - 1][cols - 1];
    }
}

Assessment trap

Do not optimize a 2D table to 1D until you can prove which previous values are still needed.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Return the minimum path sum from top-left to bottom-right moving only down or right.
Return max money without robbing adjacent houses.
Return the length of the longest subsequence shared by two strings.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Checkout risk grid	Run path search repeatedly for every cell.	Fill dp[row][col] from top and left.	Table order follows movement constraints.
Sequence scoring	Use nested brute force for every prefix.	Use dp[i] if one index summarizes the prefix.	State dimension should match changing variables.
Text comparison	Compare all subsequences directly.	Use dp[i][j] for two-string prefix comparison.	Subsequence problems often need two coordinates.

Solved modelInterview Question Solutions

Question 1: Minimum Path Sum

Return the minimum path sum from top-left to bottom-right moving only down or right. Use 2D grid DP where each cell depends on top and left.

class MinPathSum {
    static int minPathSum(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == 0 && c == 0) dp[r][c] = grid[r][c];
                else {
                    int up = r > 0 ? dp[r - 1][c] : Integer.MAX_VALUE / 2;
                    int left = c > 0 ? dp[r][c - 1] : Integer.MAX_VALUE / 2;
                    dp[r][c] = grid[r][c] + Math.min(up, left);
                }
            }
        }
        return dp[rows - 1][cols - 1];
    }
}

Question 2: House Robber

Return max money without robbing adjacent houses. 1D DP with recurrence max(skip current, rob current plus best two back).

class HouseRobber {
    static int rob(int[] nums) {
        int twoBack = 0, oneBack = 0;
        for (int value : nums) {
            int current = Math.max(oneBack, twoBack + value);
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Question 3: Longest Common Subsequence

Return the length of the longest subsequence shared by two strings. Use dp[i][j] for prefixes. If chars match, extend diagonal; otherwise take best of dropping one char.

class LCS { 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++) dp[i][j]=a.charAt(i-1)==b.charAt(j-1)?1+dp[i-1][j-1]:Math.max(dp[i-1][j],dp[i][j-1]); return dp[a.length()][b.length()]; } }

Solved modelWorked Interview Answer

Compute minimum path sum in a grid using 2D DP. Each cell depends only on the cheapest cost from top or left, so row-major fill order makes dependencies available.

class MinPathSum {
    static int minPathSum(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == 0 && c == 0) dp[r][c] = grid[r][c];
                else {
                    int up = r > 0 ? dp[r - 1][c] : Integer.MAX_VALUE / 2;
                    int left = c > 0 ? dp[r][c - 1] : Integer.MAX_VALUE / 2;
                    dp[r][c] = grid[r][c] + Math.min(up, left);
                }
            }
        }
        return dp[rows - 1][cols - 1];
    }
}

Hands-on drillTry It Yourself

Practice task

For a 3x3 grid, fill min path sum by hand. Mark which previous cells each answer depends on.

Failure patternsCommon Mistakes to Avoid

Wrong fill order.
Mixing row and column boundaries.
Optimizing space before proving dependencies.
Forgetting first row/column base cases.
Confusing subsequence with substring.

Execution guardrailQuick-Start Checklist

Identify changing variables.
Choose 1D or 2D state.
Initialize boundaries.
Fill in dependency-safe order.
State table size.
Optimize only after correctness.

Recall drillKnowledge Check

Question	Strong answer
When is DP 2D?	Two changing variables are needed.
What does fill order protect?	Dependencies are computed before they are read.
What is rolling array optimization?	Keeping only needed previous row/state.

VocabularyKey Terms

Term	Meaning
1D DP	State with one changing coordinate.
2D DP	State with two changing coordinates.
Grid DP	DP over row and column.
LCS	Longest common subsequence.

Next practiceFurther Reading

Practice min path sum, unique paths, LCS, and edit distance.
Review table visualization.
Compare substring and subsequence DP.

DP State Design

Memoization vs Tabulation