Unique Paths in Grid DP in DSA Go

Mental Model

Count how many ways to move from top-left to bottom-right in a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south. You want to know how many different routes you can take to reach your friend's house at the bottom-right corner.

Start (S) at top-left, End (E) at bottom-right in a 3x3 grid:
S -> [] -> []
↓    ↓    ↓
[] -> [] -> []
↓    ↓    ↓
[] -> [] -> E

Dry Run Walkthrough

Input: grid size: 3 rows x 3 columns

Goal: Find total unique paths from top-left to bottom-right moving only right or down

Step 1: Initialize a 3x3 matrix with 1s in first row and first column

[1, 1, 1]
[1, 0, 0]
[1, 0, 0]

Why: Only one way to reach cells in first row (all right moves) and first column (all down moves)

Step 2: Calculate paths for cell (1,1) as sum of top (0,1) and left (1,0)

[1, 1, 1]
[1, 2, 0]
[1, 0, 0]

Why: Paths to (1,1) come from above and left cells

Step 3: Calculate paths for cell (1,2) as sum of top (0,2) and left (1,1)

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

Why: Add paths from above and left to get total ways to (1,2)

Step 4: Calculate paths for cell (2,1) as sum of top (1,1) and left (2,0)

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

Why: Paths to (2,1) come from above and left

Step 5: Calculate paths for cell (2,2) as sum of top (1,2) and left (2,1)

[1, 1, 1]
[1, 2, 3]
[1, 3, 6]

Why: Final cell paths are sum of paths from above and left

Result:

Final matrix:
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
Answer: 6 unique paths

Annotated Code

DSA Go

package main

import "fmt"

func uniquePaths(m int, n int) int {
    // Create 2D slice to store path counts
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // Initialize first row and first column with 1
    for i := 0; i < m; i++ {
        dp[i][0] = 1 // only one way down
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1 // only one way right
    }

    // Fill dp table
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] // sum paths from top and left
        }
    }

    return dp[m-1][n-1] // bottom-right corner
}

func main() {
    m, n := 3, 3
    result := uniquePaths(m, n)
    fmt.Println(result)
}

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

Create 2D grid to store number of paths to each cell

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

Initialize first row and column with 1 because only one way to reach those cells

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

Calculate paths for each cell as sum of paths from above and left cells

return dp[m-1][n-1]

Return total unique paths to bottom-right cell

Output

6

Complexity Analysis

Time: O(m*n) because we fill each cell in the grid once

Space: O(m*n) for the dp table storing paths count for each cell

vs Alternative: Compared to recursive approach without memoization which is exponential, DP is efficient and avoids repeated calculations

Edge Cases

1x1 grid

Returns 1 because start is also the end

DSA Go

dp[m-1][n-1]

1 row grid (e.g., 1x5)

Returns 1 because only one way to move right

DSA Go

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

1 column grid (e.g., 5x1)

Returns 1 because only one way to move down

DSA Go

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

When to Use This Pattern

When you see a grid and need to count paths with restricted moves (right/down), use DP to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing first row and column with 1, causing incorrect path counts
Fix: Explicitly set dp[i][0] and dp[0][j] to 1 before filling the rest

Mistake: Using recursion without memoization leading to slow exponential time
Fix: Use DP table to store intermediate results and avoid repeated work

Summary

Calculates number of unique paths in a grid moving only right or down.

Use when counting ways to reach a point in a grid with movement restrictions.

Each cell's paths count is sum of paths from the cell above and the cell to the left.

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