Unique Paths in Grid DP in DSA Python - 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 large grids. The goal is to find the total number of unique routes without obstacles.

Why it matters

Without this method, counting all possible paths would take too long because the number of paths 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 storing answers to smaller parts. It helps in real-life situations like robot navigation, game moves, or planning routes where you want to know all possible ways to reach a destination.

Where it fits

Before learning this, you should understand basic loops, arrays (lists), and simple recursion. After this, you can explore more complex dynamic programming problems like those with obstacles, variable moves, or minimum path sums. This topic is a stepping stone to mastering grid-based DP and combinatorial counting.

Mental Model

Core Idea

The number of unique paths to a cell equals the sum of unique paths to the cell above it and the cell to its left.

Think of it like...

Imagine walking through a city grid where you can only move east or south. To reach any intersection, you can come either from the street above or the street to the left. Counting all ways to get there means adding the ways to get to those two streets.

Grid with cells showing path counts:

┌───┬───┬───┬───┐
│ 1 │ 1 │ 1 │ 1 │
├───┼───┼───┼───┤
│ 1 │ 2 │ 3 │ 4 │
├───┼───┼───┼───┤
│ 1 │ 3 │ 6 │10 │
└───┴───┴───┴───┘

Each number is the sum of the number above and to the left.

Build-Up - 7 Steps

1

Foundation

Understanding the Grid Movement Rules

Concept: You can only move right or down in the grid from the start to the end.

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

Result

You know the allowed moves and the start and end points.

Knowing allowed moves sets the problem boundaries and simplifies counting paths.

2

Foundation

Counting Paths Without Repetition

Concept: Each path is a sequence of moves right and down; counting all means exploring all sequences.

If you try to list all paths by moving right or down, you quickly see the number grows fast. For a 2x2 grid, there are 2 paths; for 3x3, there are 6 paths. This shows the problem grows combinatorially.

Result

You realize brute force listing is slow and inefficient for bigger grids.

Understanding the growth of paths motivates the need for a better method than brute force.

3

Intermediate

Dynamic Programming Table Setup

Concept: Use a 2D table to store the number of unique paths to each cell.

Create a 2D list dp with the same size as the grid. Initialize the first row and first column with 1 because there is only one way to reach cells in the first row (all rights) or first column (all downs).

Result

A table where dp[i][j] will hold the count of unique paths to cell (i,j).

Storing intermediate results avoids recalculating paths repeatedly.

4

Intermediate

Filling the DP Table with Recurrence

🤔Before reading on: do you think the number of paths to a cell depends on the cells above and to the left, or on all previous cells in the grid? Commit to your answer.

Concept: Each cell's path count is the sum of the counts from the cell above and the cell to the left.

For each cell dp[i][j], calculate dp[i][j] = dp[i-1][j] + dp[i][j-1]. This works because you can only come from above or left. Fill the table row by row or column by column.

Result

The bottom-right cell dp[m-1][n-1] contains the total unique paths.

This recurrence relation is the heart of the solution and captures the problem's structure.

5

Intermediate

Implementing Unique Paths in Python

Concept: Translate the DP logic into runnable Python 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] # Example: unique_paths(3, 3) returns 6

Result

Calling unique_paths(3, 3) returns 6, the number of unique paths in a 3x3 grid.

Implementing the DP table solidifies understanding and shows how theory becomes code.

6

Advanced

Optimizing Space Usage in DP

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

Concept: Since each dp cell depends only on the current row and the previous row, we can use a 1D array to save space.

Use a 1D list dp of size n initialized with 1s. Update dp[j] = dp[j] + dp[j-1] for each row. This way, dp[j] always holds the number of paths to cell (current_row, j).

Result

The function uses O(n) space instead of O(m*n) but returns the same result.

Knowing dependencies lets us reduce memory, which is important for large grids.

7

Expert

Handling Obstacles and Variations

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

Concept: Modify the DP to skip cells with obstacles by setting their path count to zero.

If a cell has an obstacle, dp[i][j] = 0 because you cannot pass through it. For other cells, dp[i][j] = dp[i-1][j] + dp[i][j-1] if no obstacle. This adapts the solution to real-world constraints.

Result

The DP table correctly counts paths avoiding obstacles, returning zero if no path exists.

Extending the DP to obstacles shows its flexibility and practical use in complex scenarios.

Under the Hood

The DP table stores the count of unique paths to each cell by building up from the base cases (first row and column). Each cell's value depends only on two neighbors: above and left. This dependency creates overlapping subproblems, which DP solves by storing results to avoid repeated calculations. Internally, this reduces an exponential problem to polynomial time.

Why designed this way?

The problem's constraints (only right and down moves) create a simple dependency pattern that fits DP perfectly. Early brute force methods were too slow. DP was chosen because it breaks the problem into smaller, manageable parts and reuses solutions, making it efficient and scalable.

┌───────────────┐
│ Start (0,0)   │
│ dp[0][0] = 1 │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ dp[i][j] =    │
│ dp[i-1][j] +  │
│ dp[i][j-1]    │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ End (m-1,n-1) │
│ dp[m-1][n-1]  │
│ = total paths │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the number of unique paths depends on the order of moves or just the count of moves? Commit to yes or no.

Common Belief: The order of moves matters, so paths with the same moves in different orders count as different.

Reality: Each unique path is defined by the sequence of moves, so different orders count as different paths. But the DP counts all sequences correctly by summing paths from above and left.

Why it matters: Misunderstanding this leads to incorrect counting or attempts to simplify the problem wrongly.

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 require a different approach.

Why it matters: Allowing diagonal moves without adjusting the solution leads to wrong path counts and confusion.

Quick: Do you think the DP table must be fully filled before getting the answer? Commit to yes or no.

Common Belief: You must fill the entire DP table before you can know the number of unique paths.

Reality: You can fill the DP table row by row or column by column, and the answer is available once the bottom-right cell is computed. Partial filling is possible if you only need certain cells.

Why it matters: Believing you must fill the whole table can waste time and memory in large grids.

Quick: Do you think the number of unique paths can be calculated using simple multiplication of rows and columns? Commit to yes or no.

Common Belief: The number of unique paths is just rows multiplied by columns.

Reality: The number of unique paths is a combinatorial count, not a simple product. It equals the binomial coefficient C(m+n-2, m-1).

Why it matters: Using multiplication instead of combinatorics or DP leads to wrong answers and misunderstanding of the problem's nature.

Expert Zone

1

The DP solution exploits the problem's monotonic movement constraints, which means no cycles or backward moves, simplifying dependencies.

2

The combinatorial formula for unique paths (binomial coefficient) is mathematically equivalent to the DP result but requires understanding combinations and factorials.

3

Space optimization from 2D to 1D DP arrays is possible because each row depends only on the previous row, a subtle but powerful insight for memory efficiency.

When NOT to use

This DP approach is not suitable if moves are allowed in more directions (like diagonal or backward), or if the grid has complex obstacles requiring path validation. In such cases, graph traversal algorithms like BFS or DFS, or more advanced DP with state tracking, should be used.

Production Patterns

In real systems, this DP pattern is used in robot path planning, game AI for move counting, and network routing where only certain moves are allowed. It also appears in combinatorial optimization problems and is a foundation for more complex grid-based DP tasks.

Connections

Binomial Coefficients

Equivalent mathematical formula for counting unique paths

Understanding the combinatorial formula helps verify DP results and connects counting paths to probability and combinatorics.

Graph Traversal Algorithms

Alternative approach for path counting in grids with complex moves or obstacles

Knowing when to switch from DP to graph algorithms improves problem-solving flexibility in pathfinding tasks.

Urban Planning and Traffic Flow

Real-world analogy of grid movement and route counting

Recognizing that city street layouts and traffic routing problems share the same structure as grid path counting reveals the practical impact of this concept.

Common Pitfalls

#1 Trying to count paths by multiplying rows and columns directly.

Wrong approach:

def unique_paths(m, n):
return m * n

Correct approach:

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]

Root cause:

Misunderstanding that path counting is combinatorial, not a simple product.

#2 Allowing diagonal moves without adjusting the DP logic.

Wrong approach:

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] + dp[i-1][j-1] # diagonal added incorrectly
return dp[m-1][n-1]

Correct approach:

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] # only right and down
return dp[m-1][n-1]

Root cause:

Confusing problem constraints and adding moves not allowed by the problem.

#3 Not initializing the first row and column to 1.

Wrong approach:

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

Correct approach:

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]

Root cause:

Forgetting base cases causes index errors or wrong sums.

Key Takeaways

Unique Paths in Grid DP counts all ways to move from top-left to bottom-right by only moving right or down.

Dynamic programming stores intermediate results to avoid repeated counting, making the solution efficient.

Each cell's path count depends only on the cell above and the cell to the left, forming a simple recurrence.

Space can be optimized from a 2D table to a 1D array by understanding dependencies.

The problem connects deeply to combinatorics and real-world pathfinding scenarios, showing DP's power and flexibility.

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