Unique Paths in Grid DP in DSA Python - 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

↓

Repeat until bottom-right cell

↓

Return dp[m-1

We fill a table where each cell counts paths from start by adding paths from top and left cells, starting with 1s on first row and column.

Execution Sample

DSA Python

def unique_paths(m, n):
    dp = [[1]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

Calculates number of unique paths in an m x n grid moving only right or down.

Execution Table

Step	Operation	Cell Updated	Value Computed	DP Table State
Init	Create DP table with 1s in first row and column	All cells in row 0 and column 0	1	[[1, 1, 1], [1, 1, 1], [1, 1, 1]]
1	Calculate dp[1][1] = dp[0][1] + dp[1][0]	(1,1)	1 + 1 = 2	[[1, 1, 1], [1, 2, 1], [1, 1, 1]]
2	Calculate dp[1][2] = dp[0][2] + dp[1][1]	(1,2)	1 + 2 = 3	[[1, 1, 1], [1, 2, 3], [1, 1, 1]]
3	Calculate dp[2][1] = dp[1][1] + dp[2][0]	(2,1)	2 + 1 = 3	[[1, 1, 1], [1, 2, 3], [1, 3, 1]]
4	Calculate dp[2][2] = dp[1][2] + dp[2][1]	(2,2)	3 + 3 = 6	[[1, 1, 1], [1, 2, 3], [1, 3, 6]]
End	Return dp[m-1][n-1]	(2,2)	6	Final answer: 6 unique paths

💡 All cells computed, bottom-right cell dp[2][2] holds total unique paths

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
dp	[[1,1,1],[1,1,1],[1,1,1]]	[[1,1,1],[1,2,1],[1,1,1]]	[[1,1,1],[1,2,3],[1,1,1]]	[[1,1,1],[1,2,3],[1,3,1]]	[[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 fill the first row and first column with 1s initially?

Because from the start cell, you can only move right along the first row or down along the first column, so there is exactly 1 way to reach any cell in those edges. This is shown in the 'Init' row of the execution_table.

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 paths to (i,j) is sum of paths to those two cells. See steps 1 to 4 in execution_table.

What does dp[m-1][n-1] represent at the end?

It represents the total number of unique paths from the top-left to bottom-right cell, after filling the whole DP table. This is confirmed in the 'End' step of execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the value computed for dp[2][1]?

A 2

B 4

C 3

D 6

💡 Hint

Check the 'Value Computed' column at Step 3 in execution_table.

At which step does the condition to stop filling the DP table occur?

A Step 2

B End

C Step 4

D Init

💡 Hint

Look at the 'exit_note' and the 'End' row in execution_table.

If the grid size was 2x2 instead of 3x3, what would be the final dp[m-1][n-1] value?

A 2

B 3

C 4

D 1

💡 Hint

Think about the smaller DP table initialization and filling logic shown in variable_tracker.

Concept Snapshot

Unique Paths DP:
- Create m x n table dp
- Fill first row and column with 1
- For each cell dp[i][j] = dp[i-1][j] + dp[i][j-1]
- dp[m-1][n-1] holds total unique paths
- Moves allowed: right or down only

Full Transcript

This concept shows how to find the number of unique paths in a grid from top-left to bottom-right moving only right or down. We create a table dp where each cell stores the count of ways to reach it. We start by filling the first row and first column with 1 because there is only one way to reach those cells by moving straight right or down. Then for each other cell, we add the number of ways to reach the cell above and the cell to the left. This process continues until we fill the entire table. The value in the bottom-right cell is the total number of unique paths. The execution table traces each step of filling the dp table, showing how values are computed and how the table changes. Key moments clarify why the first row and column are 1, why we add top and left cells, and what the final dp value means. The visual quiz tests understanding of specific steps and the final result. This method uses dynamic programming to efficiently count paths without enumerating them all.

Practice

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

easy

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

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

C. The number of ways to move from top-left to bottom-right in a grid moving only right or down

D. The number of obstacles in the grid

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible ways to reach the bottom-right cell from the top-left cell by moving only right or down.

2. Step 2: Clarify movement constraints

   Only moves allowed are right or down, so paths are unique sequences of these moves.

3. Final Answer:

   The number of ways to move from top-left to bottom-right in a grid moving only right or down -> Option C

4. Quick Check:

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

Hint: Count paths by moving only right or down [OK]

Common Mistakes:

• Thinking about shortest path length instead of count
• Including diagonal moves
• Confusing with maximum sum path

2. Which of the following Python code snippets correctly initializes a 2D list dp of size m x n with all values set to 1?

easy

A. dp = [[1]*m for _ in range(n)]

B. dp = [[1]*n for _ in range(m)]

C. dp = [[1]*n]*m

D. dp = [1]*m*n

Solution

1. Step 1: Understand 2D list initialization

   We want a list with m rows and n columns, each cell initialized to 1.

2. Step 2: Check each option

   dp = [[1]*n for _ in range(m)] uses list comprehension correctly to create m lists each of length n. dp = [[1]*m for _ in range(n)] swaps m and n. dp = [[1]*n]*m creates shallow copies causing aliasing issues. dp = [1]*m*n creates a flat list, not 2D.

3. Final Answer:

   dp = [[1]*n for _ in range(m)] -> Option B

4. Quick Check:

   Correct 2D list init = dp = [[1]*n for _ in range(m)] [OK]

Hint: Use list comprehension for 2D lists to avoid aliasing [OK]

Common Mistakes:

• Using [[1]*n]*m causing all rows to reference same list
• Swapping m and n dimensions
• Creating flat list instead of 2D

3. What is the output of the following code?

def unique_paths(m, n):
    dp = [[1]*n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 3))

medium

A. 6

B. 3

C. 9

D. 1

Solution

1. Step 1: Understand DP table filling

   dp[i][j] stores number of unique paths to cell (i,j). First row and column are 1 because only one way to reach them.

2. Step 2: Calculate dp values for 3x3 grid

   dp[1][1] = dp[0][1] + dp[1][0] = 1+1=2
   dp[1][2] = dp[0][2] + dp[1][1] = 1+2=3
   dp[2][1] = dp[1][1] + dp[2][0] = 2+1=3
   dp[2][2] = dp[1][2] + dp[2][1] = 3+3=6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum paths from top and left neighbors [OK]

Common Mistakes:

• Returning dp[m][n] instead of dp[m-1][n-1]
• Not initializing first row and column to 1
• Mixing up indices in loops

4. Find the error in the following code for unique paths and select the fix:

def unique_paths(m, n):
    dp = [[0]*n]*m
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

medium

A. Return dp[m][n] instead of dp[m-1][n-1]

B. Change loops to start from 0 instead of 1

C. Initialize dp with ones instead of zeros

D. Change dp initialization to dp = [[0]*n for _ in range(m)]

Solution

1. Step 1: Identify dp initialization problem

   Using dp = [[0]*n]*m creates shallow copies of the same row, so updating one row updates all rows.

2. Step 2: Fix dp initialization

   Use list comprehension dp = [[0]*n for _ in range(m)] to create independent rows.

3. Final Answer:

   Change dp initialization to dp = [[0]*n for _ in range(m)] -> Option D

4. Quick Check:

   Independent rows fix aliasing issue [OK]

Hint: Use list comprehension for 2D list to avoid shared references [OK]

Common Mistakes:

• Using [[0]*n]*m causing all rows to be same object
• Changing loop ranges unnecessarily
• Returning wrong dp index

5. Given a grid with obstacles represented by 1s and empty spaces by 0s, how would you modify the unique paths DP solution to count paths avoiding obstacles?
Choose the correct approach:

hard

A. Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], initialize dp[0][0] = 1 if no obstacle

B. Ignore obstacles and run normal unique paths DP

C. Set dp[i][j] = 1 for obstacles and 0 otherwise

D. Use recursion without memoization to handle obstacles

Solution

1. Step 1: Handle obstacles in DP initialization

   If a cell has an obstacle (1), no paths can go through it, so dp[i][j] = 0.

2. Step 2: Update dp values considering obstacles

   For empty cells (0), dp[i][j] = sum of paths from top and left neighbors if they are not blocked.

3. Final Answer:

   Set dp[i][j] = 0 if grid[i][j] == 1; else dp[i][j] = dp[i-1][j] + dp[i][j-1], initialize dp[0][0] = 1 if no obstacle -> Option A

4. Quick Check:

   Obstacles block paths, so dp = 0 there [OK]

Hint: Set dp to 0 at obstacles, sum neighbors otherwise [OK]

Common Mistakes:

• Ignoring obstacles in DP calculation
• Setting dp=1 at obstacle cells
• Using recursion without memo causing inefficiency