Unique Paths in Grid DP in DSA Go - Execution Trace

Concept Flow - Unique Paths in Grid DP

Start at top-left cell

↓

Initialize DP table with 1s in first row and column

↓

For each cell (i,j) from (1,1) to (m-1,n-1)

↓

Calculate dp[i

↓

Fill DP table row by row

↓

Result is dp[m-1

We fill a table where each cell shows how many ways to reach it from the start by summing ways from the top and left cells.

Execution Sample

DSA Go

func uniquePaths(m, n int) int {
 dp := make([][]int, m)
 for i := range dp {
  dp[i] = make([]int, n)
  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]
}

This code counts unique paths in a grid by building a DP table where each cell sums paths from above and left.

Execution Table

Step	Operation	Cell Updated	DP Table State	Explanation
1	Initialize first column	(0,0)	[[1,0,0],[1,0,0],[1,0,0]]	Set first column cells to 1 (only one way down)
2	Initialize first row	(0,0)	[[1,1,1],[1,0,0],[1,0,0]]	Set first row cells to 1 (only one way right)
3	Calculate dp[1][1]	(1,1)	[[1,1,1],[1,2,0],[1,0,0]]	dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2
4	Calculate dp[1][2]	(1,2)	[[1,1,1],[1,2,3],[1,0,0]]	dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3
5	Calculate dp[2][1]	(2,1)	[[1,1,1],[1,2,3],[1,3,0]]	dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3
6	Calculate dp[2][2]	(2,2)	[[1,1,1],[1,2,3],[1,3,6]]	dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
7	Return result	(2,2)	[[1,1,1],[1,2,3],[1,3,6]]	Total unique paths = dp[2][2] = 6

💡 All cells filled, dp[m-1][n-1] contains total unique paths

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
dp	[[0,0,0],[0,0,0],[0,0,0]]	[[1,0,0],[1,0,0],[1,0,0]]	[[1,1,1],[1,0,0],[1,0,0]]	[[1,1,1],[1,2,0],[1,0,0]]	[[1,1,1],[1,2,3],[1,0,0]]	[[1,1,1],[1,2,3],[1,3,0]]	[[1,1,1],[1,2,3],[1,3,6]]	[[1,1,1],[1,2,3],[1,3,6]]

Key Moments - 3 Insights

Why do we set the first row and first column cells to 1 before filling the rest?

Because from the start cell, you can only move right along the first row or down along the first column, so there is exactly one way to reach those cells. This is shown in execution_table rows 1 and 2.

Why do we add dp[i-1][j] and dp[i][j-1] to get dp[i][j]?

Because to reach cell (i,j), you can only come from the cell above (i-1,j) or the cell to the left (i,j-1). So total ways are sum of ways to those two cells, as shown in execution_table rows 3 to 6.

What does dp[m-1][n-1] represent after filling the table?

It represents the total number of unique paths from the start (0,0) to the bottom-right cell (m-1,n-1), as shown in execution_table row 7.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4. What is the value of dp[1][2]?

A 1

B 2

C 3

D 6

💡 Hint

Check the DP Table State column at Step 4 in execution_table

At which step does the dp table first show a cell with value 6?

A Step 6

B Step 5

C Step 3

D Step 7

💡 Hint

Look for the DP Table State column where 6 first appears in execution_table

If we did not initialize the first row to 1, what would happen to dp[0][2] after Step 2?

A It would be 1

B It would be 0

C It would be 2

D It would be undefined

💡 Hint

Refer to variable_tracker and execution_table rows 1 and 2 about first row initialization

Concept Snapshot

Unique Paths in Grid DP:
- Use a 2D dp table of size m x n
- Initialize first row and first column to 1
- For each cell dp[i][j], dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Result is dp[m-1][n-1]
- Counts unique ways moving only right or down

Full Transcript

This concept shows how to count unique paths in a grid using dynamic programming. We create a table dp where each cell stores the number of ways to reach it from the start. We first set the first row and first column to 1 because there is only one way to reach those cells by moving right or down. Then, for each other cell, we add the number of ways from the cell above and the cell to the left. This builds up the total paths step by step. The final answer is in the bottom-right cell of the dp table. The execution table traces each update to the dp table, showing how values accumulate. The variable tracker shows the dp table state after each step. Key moments clarify why initialization is needed and how the addition works. The visual quiz tests understanding of dp values at specific steps and the importance of initialization.

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