Unique Paths in Grid DP in DSA Python

Mental Model

Count how many ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south to reach your destination. You want to know how many different routes you can take without backtracking.

Start (S) at top-left, End (E) at bottom-right:
S -> -> ->
↓   ↓   ↓
-> -> -> E

Dry Run Walkthrough

Input: Grid size: 3 rows x 3 columns

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

Step 1: Initialize first row and first column with 1 because there is only one way to reach those cells

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

Why: Only one way to move straight right or straight down to reach cells in first row or column

Step 2: Calculate paths for cell (1,1) by adding paths from 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) by adding paths from top (0,2) and left (1,1)

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

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

Step 4: Calculate paths for cell (2,1) by adding paths from 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 cells

Step 5: Calculate paths for cell (2,2) by adding paths from 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 DP grid:
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
Number of unique paths = 6

Annotated Code

DSA Python

class UniquePaths:
    def unique_paths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        # Initialize first row and first column
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        # Fill dp table
        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]

if __name__ == '__main__':
    solver = UniquePaths()
    result = solver.unique_paths(3, 3)
    print(f"Number of unique paths = {result}")

for i in range(m): dp[i][0] = 1

Set first column cells to 1 because only one way to move down

for j in range(n): dp[0][j] = 1

Set first row cells to 1 because only one way to move right

for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1]

Calculate paths for each cell by summing paths from top and left neighbors

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

Return total unique paths to bottom-right cell

Output

Number of unique paths = 6

Complexity Analysis

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

Space: O(m*n) because we store path counts for each cell in a 2D array

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

Edge Cases

Grid with 1 row or 1 column

Returns 1 because only one path exists (all right or all down moves)

DSA Python

for i in range(m):
    dp[i][0] = 1

Grid size 1x1

Returns 1 because start and end are the same cell

DSA Python

return dp[m-1][n-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 the first row and first column to 1
Fix: Explicitly set dp[i][0] and dp[0][j] to 1 before filling the rest of the table

Mistake: Adding dp[i][j-1] and dp[i-1][j] in wrong order or indices
Fix: Ensure dp[i][j] = dp[i-1][j] + dp[i][j-1] to correctly sum top and left neighbors

Summary

Calculates the number of unique ways to reach the bottom-right corner of a grid moving only right or down.

Use when you need to count paths in a grid with movement constraints.

The key insight is that paths to each cell come from the sum of paths to the cell above and to the left.

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