Dynamic Programming Base Cases for Grid Problems

Grid DP questions like Unique Paths look simple until a single obstacle or misaligned base case ruins every answer. This guide shows how to initialize rows and columns correctly, visualize the table, and keep your interview narration tight.

TL;DR

• Topic: Setting base cases for grid-based DP (paths, obstacles, minimum cost).
• Interview value: Shows you understand recurrence prerequisites, not just the formula.
• Core steps: choose table orientation, seed first row/column, handle obstacles, apply recurrence.
• Beginners often skip zeroing after obstacles, misalign i/j indices, or forget that memo defaults matter.
• You'll learn a visual template, TypeScript code, common pitfalls, and practice prompts.

Beginner-Friendly Explanations

Why Base Cases Drive Everything

Recurrences only work when neighbors are valid. If the first row or column is wrong, every downstream cell inherits errors. Treat base cases as contract setup.

Picking a Table Orientation

Decide if dp[i][j] represents row i, column j from top-left. Stick to one convention and restate it before coding—habits reinforced in the interview communication guide.

Obstacles Change the Seed

Once a cell in the first row or column is blocked, every cell beyond it in that row/column must be zero. This is the trap most tutorials skip.

Step-by-Step Learning Guidance

1) Define the State and Recurrence

For Unique Paths with obstacles: dp[i][j] = paths to (i,j). Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1] if grid[i][j] is free.

2) Initialize the Start Cell

If grid[0][0] is blocked, answer is 0. Otherwise set dp[0][0] = 1. Say this out loud to anchor the base.

3) Seed First Row and Column

Iterate j from 1..m-1 for the first row: if cell is open and previous is 1, set to 1; else 0. Do the same for i in the first column. Visualize this sweep in a table, aided by the learning tools page.

4) Fill the Rest of the Table

For each cell starting at (1,1), if blocked set 0, else sum top and left. Keep narration concise, similar to a mock interview routine.

5) Validate With Small Grids

Test 2x2, 3x3 with an obstacle at (0,1) or (1,0). Draw the table to ensure seeds zero out properly.

Visualizable Example: Unique Paths With Obstacles

function uniquePathsWithObstacles(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => Array(cols).fill(0));

  if (grid[0][0] === 1) return 0;
  dp[0][0] = 1;

  for (let j = 1; j < cols; j++) {
    dp[0][j] = grid[0][j] === 0 && dp[0][j - 1] === 1 ? 1 : 0;
  }

  for (let i = 1; i < rows; i++) {
    dp[i][0] = grid[i][0] === 0 && dp[i - 1][0] === 1 ? 1 : 0;
  }

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < cols; j++) {
      if (grid[i][j] === 0) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
  }

  return dp[rows - 1][cols - 1];
}

Notice how the first row/column stop propagating once an obstacle appears; every downstream cell stays 0.

Practical Preparation Strategies

Hand-Draw Tables

Sketch 4x4 grids with varying obstacles. Filling them by hand cements the seeding rules faster than code alone.

Alternate Orientations

Try row-major then column-major fills. Explaining the choice is interview gold and parallels the AI prep primer.

Add Minimum-Cost Variants

Replace sums with min(top, left) + cost[i][j]. The seeding logic is identical, reinforcing that base cases transcend problem flavor.

Invite Light Guidance

Tools like LeetCopilot can highlight when your seeds ignore an early obstacle, nudging you before you waste time on wrong recurrences.

Common Mistakes to Avoid

Forgetting the Starting Cell Can Be Blocked

Always check grid[0][0]; returning 0 early avoids incorrect tables.

Continuing Ones After an Obstacle

Once you hit a block in the first row/column, all cells beyond stay 0.

Mixing Indices

Be consistent with dp[i][j] meaning row i, column j. Mismatched indices cause diagonal-like errors.

Leaving Default Ones

If you initialize dp with ones, obstacles won't zero correctly. Start with zeros and seed intentionally.

FAQ

How do I know my base cases are right?

Check the first row/column after seeding; they should reflect obstacles accurately before filling the rest.

What should I practice before grid DP?

Get comfortable with 2D arrays and simpler 1D DP like climbing stairs.

Is grid DP important for interviews?

Yes—it's common for paths, costs, and counting questions, and base-case clarity is often probed.

Can I switch to 1D rolling arrays?

Yes, but only after your base cases are correct; the first row/column logic still applies.

Conclusion

Nailing DP base cases on grids prevents cascading errors and shows interviewers you think from first principles. Seed the start carefully, zero after obstacles, and your recurrences will finally produce the answers you expect.