Unique Paths in Grid DP in DSA Go - Deep Dive

Overview - Unique Paths in Grid DP

What is it?

Unique Paths in Grid DP is a way to count how many different ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down. It uses a method called dynamic programming to remember past results and avoid repeating work. This helps solve the problem efficiently even for big grids. The goal is to find the total number of unique paths without listing them all.

Why it matters

Without this method, counting paths would take too long because the number of ways grows very fast as the grid gets bigger. This problem shows how dynamic programming can turn a slow, repetitive task into a fast one by saving answers to smaller problems. It helps in many real-world tasks like robot movement, game design, and route planning where you need to count or find paths quickly.

Where it fits

Before learning this, you should understand basic loops, arrays, and simple recursion. After this, you can learn more complex dynamic programming problems like grid paths with obstacles, minimum path sum, or combinatorial problems. This topic builds a foundation for solving many grid-based and path-counting challenges.

Mental Model

Core Idea

Count paths by building up from smaller steps, remembering how many ways to reach each cell using only moves right or down.

Think of it like...

Imagine walking through a city grid where you can only go east or south. To know how many ways to reach a certain intersection, you add the ways to get to the intersection just north and just west of it.

Start (0,0)
  ↓     ->
(0,1) -> (0,2) -> ... -> (0,n-1)
  ↓       ↓           ↓
(1,0) -> (1,1) -> ... -> (1,n-1)
  ↓       ↓           ↓
...     ...         ...
  ↓       ↓           ↓
(m-1,0) -> ... -> ... -> End (m-1,n-1)

Each cell = ways to get here = ways from top + ways from left

Build-Up - 7 Steps

1

Foundation

Understanding the grid and moves

Concept: Introduce the grid layout and allowed moves (right and down).

Imagine a grid with rows and columns. You start at the top-left corner (0,0). You can only move one step right or one step down at a time. The goal is to reach the bottom-right corner (m-1,n-1).

Result

You know the problem setup: start, end, and allowed moves.

Understanding the movement rules is key because it limits the paths and makes counting possible.

2

Foundation

Brute force counting paths recursively

Concept: Count paths by trying all possible moves recursively.

Write a function that, from a cell, tries moving right and down recursively until it reaches the end. Sum all successful paths. This works but repeats many calculations.

Result

Exponential time complexity, slow for big grids.

Seeing the brute force method shows why we need a better way to avoid repeated work.

3

Intermediate

Introducing dynamic programming table

Concept: Use a 2D table to store the number of ways to reach each cell.

Create a 2D array dp with the same size as the grid. dp[i][j] will hold the number of unique paths to cell (i,j). Initialize dp[0][0] = 1 since start has one way. Then fill the table row by row or column by column.

Result

A table that builds up the count of paths for each cell.

Storing results prevents recalculating paths for the same cell multiple times.

4

Intermediate

Filling dp table with recurrence relation

🤔Before reading on: do you think the number of ways to reach a cell depends on the sum of ways from the top and left cells, or from all surrounding cells? Commit to your answer.

Concept: Each cell's paths = paths from above + paths from left.

For each cell (i,j), dp[i][j] = dp[i-1][j] + dp[i][j-1]. If i or j is 0, handle edges by setting dp[i][j] = 1 because only one path exists along edges.

Result

The dp table correctly counts unique paths for all cells.

Knowing the problem breaks down into smaller subproblems linked by this simple formula is the heart of dynamic programming here.

5

Intermediate

Implementing DP solution in Go

Concept: Translate the dp logic into Go code with loops and arrays.

Use nested loops to fill dp. Initialize dp with size m x n. Set dp[0][0] = 1. For first row and column, set dp[i][0] = 1 and dp[0][j] = 1. Then fill dp[i][j] = dp[i-1][j] + dp[i][j-1]. Return dp[m-1][n-1].

Result

Efficient code that returns the total unique paths count.

Implementing the logic solidifies understanding and shows how theory becomes working code.

6

Advanced

Optimizing space usage in DP

🤔Before reading on: do you think we need to store the entire 2D dp table, or can we use less memory? Commit to your answer.

Concept: Use a single 1D array to save space since only the current and previous row are needed.

Create a 1D array dp of size n. Initialize all elements to 1 (first row). For each next row, update dp[j] = dp[j] + dp[j-1]. This accumulates paths using only one array.

Result

Memory usage reduced from O(m*n) to O(n) without changing the result.

Recognizing overlapping data lets us optimize memory, a key skill for efficient algorithms.

7

Expert

Handling obstacles and extensions

🤔Before reading on: do you think the same dp formula works if some cells are blocked? Commit to your answer.

Concept: Modify dp to skip blocked cells by setting their paths to zero.

If a cell is blocked, set dp[i][j] = 0. Otherwise, use dp[i][j] = dp[i-1][j] + dp[i][j-1]. This adapts the solution to real-world grids with obstacles.

Result

The dp table correctly counts paths avoiding obstacles.

Adapting the core idea to handle constraints shows the flexibility and power of dynamic programming.

Under the Hood

The algorithm builds a table where each cell stores the count of unique paths to reach it. It uses the fact that to get to a cell, you must come from either the cell above or the cell to the left. By summing these counts, it accumulates the total paths. This avoids recalculating paths multiple times, which happens in naive recursion.

Why designed this way?

Dynamic programming was designed to solve problems with overlapping subproblems and optimal substructure. Counting unique paths fits perfectly because each cell's count depends only on two previous cells. This design reduces exponential time to polynomial time, making large problems solvable.

┌─────────────┐
│ Start (0,0) │
└─────┬───────┘
      │
      ▼
┌─────────────┐     ┌─────────────┐
│ dp[i-1][j]  │ +->  │ dp[i][j-1]  │
└─────┬───────┘     └─────┬───────┘
      │                   │
      ▼                   ▼
  ┌─────────────┐
  │ dp[i][j]    │
  └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the number of unique paths can be found by multiplying the number of rows and columns? Commit to yes or no.

Common Belief: The total unique paths equal rows times columns.

Reality: The number of unique paths grows combinatorially, not linearly, and equals combinations of moves, not just multiplication.

Why it matters: Using multiplication underestimates or overestimates paths, leading to wrong answers in planning or algorithms.

Quick: Do you think you can move diagonally in the unique paths problem? Commit to yes or no.

Common Belief: You can move diagonally as well as right and down.

Reality: Only right and down moves are allowed; diagonal moves change the problem and path counts.

Why it matters: Allowing diagonal moves changes the problem's nature and invalidates the dp formula, causing incorrect results.

Quick: Do you think the dp table must be fully filled before reading any result? Commit to yes or no.

Common Belief: You must fill the entire dp table before you can know any cell's path count.

Reality: You can compute cells row by row or column by column, and partial results are valid as soon as computed.

Why it matters: Understanding partial computation allows optimizations and early stopping in some cases.

Quick: Do you think the dp solution always uses a 2D array? Commit to yes or no.

Common Belief: Dynamic programming for unique paths always requires a 2D dp array.

Reality: You can optimize space to use a 1D array because each row depends only on the previous row.

Why it matters: Knowing space optimization helps write efficient code for large grids.

Expert Zone

1

The order of filling the dp table matters; row-major or column-major both work but must be consistent.

2

Space optimization relies on the problem's property that only the previous row is needed, which is not always true in other dp problems.

3

When obstacles are introduced, careful initialization of dp edges is required to avoid counting invalid paths.

When NOT to use

This approach is not suitable if moves other than right and down are allowed, or if the grid is infinite or has complex constraints. In such cases, graph traversal algorithms like BFS or DFS, or combinatorial math, might be better.

Production Patterns

In real systems, this pattern is used in robot path planning, game AI for grid movement, and network routing where counting or finding paths with constraints is needed. Space-optimized dp is preferred for memory-limited environments.

Connections

Pascal's Triangle

The unique paths count corresponds to binomial coefficients found in Pascal's Triangle.

Understanding this connection reveals a direct combinatorial formula for unique paths, linking dynamic programming to combinatorics.

Graph Theory

The grid can be seen as a directed graph where edges represent allowed moves; counting unique paths is counting paths in this graph.

Viewing the problem as graph traversal helps apply graph algorithms and understand path counting in networks.

Probability Theory

Counting unique paths relates to calculating probabilities of sequences of moves in a grid-based random walk.

This connection helps in modeling and analyzing random processes and decision-making under uncertainty.

Common Pitfalls

#1 Ignoring edge cases for first row and first column initialization.

Wrong approach:

for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}

Correct approach:

for i := 0; i < m; i++ {
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}

Root cause:

Not handling the first row and column separately causes index errors and wrong path counts.

#2 Using recursion without memoization leading to exponential time.

Wrong approach:

func uniquePaths(i, j int) int {
if i == 0 && j == 0 {
return 1
}
if i < 0 || j < 0 {
return 0
}
return uniquePaths(i-1, j) + uniquePaths(i, j-1)
}

Correct approach:

Use a dp table or memo map to store results and avoid repeated calls.

Root cause:

Ignoring overlapping subproblems causes repeated calculations and slow performance.

#3 Not updating dp array correctly in space-optimized version.

Wrong approach:

for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] = dp[j-1]
}
}

Correct approach:

for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] = dp[j] + dp[j-1]
}
}

Root cause:

Overwriting dp[j] without adding previous value loses path counts.

Key Takeaways

Unique Paths in Grid DP counts ways to reach each cell by summing paths from the top and left cells.

Dynamic programming avoids repeated work by storing intermediate results in a table or array.

Proper initialization of the first row and column is crucial for correct path counts.

Space optimization is possible because each row depends only on the previous row's data.

The problem connects deeply to combinatorics, graph theory, and probability, showing its broad relevance.

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?
Unique Paths means:

easy

A. The shortest path length from top-left to bottom-right in a grid

B. The number of ways to move from top-left to bottom-right in a grid using only right and down moves

C. The maximum sum path from top-left to bottom-right in a grid

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible paths from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Identify the meaning of "Unique Paths"

   Unique paths means counting distinct ways, not shortest or maximum sum paths.

3. Final Answer:

   The number of ways to move from top-left to bottom-right in a grid using only right and down moves -> Option B

4. Quick Check:

   Unique Paths = Count of right/down moves paths [OK]

Hint: Unique Paths count all right/down routes from start to end [OK]

Common Mistakes:

• Confusing unique paths with shortest path length
• Thinking about obstacles when none are given
• Mixing path count with path sum

2. Which of the following Go code snippets correctly initializes a 2D slice dp of size m x n with zeros for Unique Paths DP?

easy

A. dp := [][]int{}
dp = append(dp, make([]int, m))
dp = append(dp, make([]int, n))

B. dp := make([]int, m*n)
for i := 0; i < m*n; i++ {
dp[i] = 0
}

C. var dp [m][n]int
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
dp[i][j] = 1
}
}

D. dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}

Solution

1. Step 1: Understand Go slice initialization for 2D arrays

   In Go, a 2D slice is created by first making the outer slice, then initializing each inner slice.

2. Step 2: Check each option

   dp := make([][]int, m) for i := range dp { dp[i] = make([]int, n) } correctly creates a slice of length m, then each inner slice of length n, all initialized to zero by default.

3. Final Answer:

   dp := make([][]int, m) for i := range dp { dp[i] = make([]int, n) } -> Option D

4. Quick Check:

   2D slice init with nested make loops = dp := make([][]int, m) for i := range dp { dp[i] = make([]int, n) } [OK]

Hint: Use nested make to create 2D slices in Go [OK]

Common Mistakes:

• Using one-dimensional slice for 2D data
• Initializing inner slices with wrong length
• Appending slices incorrectly

3. What is the output of the following Go code for Unique Paths in a 3x3 grid?

func uniquePaths(m, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

fmt.Println(uniquePaths(3, 3))

medium

A. 3

B. 9

C. 6

D. 1

Solution

1. Step 1: Initialize dp with 1s on first row and column

   First row and first column are set to 1 because only one way to reach those cells (all right or all down).

2. Step 2: Fill dp table using dp[i][j] = dp[i-1][j] + dp[i][j-1]

   Calculate paths for each cell by summing paths from top and left cells. For 3x3 grid, dp[2][2] = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Use dp[i][j] = dp[i-1][j] + dp[i][j-1] to fill grid [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Using wrong indices in dp update
• Returning wrong dp cell

4. The following Go code for Unique Paths has a bug. What is the error?

func uniquePaths(m, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] * dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

medium

A. The dp update uses multiplication instead of addition

B. The dp slice is not initialized properly

C. The loops for initializing first row and column are swapped

D. The function returns dp[0][0] instead of dp[m-1][n-1]

Solution

1. Step 1: Check dp update formula

   The code uses dp[i][j] = dp[i-1][j] * dp[i][j-1], which multiplies paths instead of adding them.

2. Step 2: Correct formula for Unique Paths

   The correct formula is dp[i][j] = dp[i-1][j] + dp[i][j-1] to sum the number of ways from top and left cells.

3. Final Answer:

   The dp update uses multiplication instead of addition -> Option A

4. Quick Check:

   Use addition, not multiplication in dp update [OK]

Hint: Sum paths from top and left, don't multiply [OK]

Common Mistakes:

• Using * instead of + in dp update
• Forgetting to initialize first row/column
• Returning wrong dp cell

5. Given a 4x4 grid with some obstacles represented by 1s, how would you modify the Unique Paths DP approach to count paths avoiding obstacles?
Obstacles grid:

0 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0

hard

A. Set dp[i][j] = 0 if obstacle at (i,j), else dp[i][j] = dp[i-1][j] + dp[i][j-1]

B. Ignore obstacles and use normal dp formula

C. Set dp[i][j] = 1 if obstacle at (i,j), else 0

D. Use multiplication of dp[i-1][j] and dp[i][j-1] for obstacles

Solution

1. Step 1: Identify obstacle handling in DP

   When a cell has an obstacle, no path can go through it, so dp[i][j] must be 0.

2. Step 2: Modify dp update to skip obstacles

   For cells without obstacles, dp[i][j] = dp[i-1][j] + dp[i][j-1]. For obstacles, dp[i][j] = 0.

3. Final Answer:

   Set dp[i][j] = 0 if obstacle at (i,j), else dp[i][j] = dp[i-1][j] + dp[i][j-1] -> Option A

4. Quick Check:

   Obstacles block paths, set dp to zero there [OK]

Hint: Zero dp at obstacles, sum paths otherwise [OK]

Common Mistakes:

• Ignoring obstacles in dp calculation
• Setting dp to 1 at obstacles
• Multiplying dp values instead of adding