Unique Paths in Grid DP in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the problem statement of Unique Paths in Grid DP?

Find the number of unique ways to move from the top-left corner to the bottom-right corner of a grid, moving only down or right.

beginner

What does the DP table represent in Unique Paths problem?

Each cell in the DP table represents the number of unique ways to reach that cell from the start (top-left corner).

beginner

How do you calculate the number of unique paths to a cell (i, j)?

Number of ways to (i, j) = ways to (i-1, j) + ways to (i, j-1), because you can only come from above or left.

beginner

Why do we initialize the first row and first column with 1 in Unique Paths DP?

Because there is only one way to reach any cell in the first row (all moves right) or first column (all moves down).

beginner

What is the time complexity of the DP solution for Unique Paths?

O(m * n), where m is number of rows and n is number of columns, since we fill each cell once.

In Unique Paths, from which directions can you move to reach a cell?

A From above or from left

B From below or from right

C From diagonal only

D From any direction

You can only move down or right, so to reach a cell, you come from above or left.

What value do you assign to the first cell (top-left) in the DP table?

A 0

B 1

C Number of rows

D Number of columns

The start cell has 1 way to be reached (starting point).

If the grid size is 3x3, how many unique paths are there from top-left to bottom-right?

A 6

B 3

C 9

D 12

For 3x3 grid, unique paths = 6.

What is the main idea behind using DP for Unique Paths?

A Try all paths recursively without memoization

B Use sorting to find paths

C Store number of ways to reach each cell to avoid recomputation

D Use greedy approach

DP stores results for subproblems to avoid repeated calculations.

Which cells in the DP table are initialized to 1 before filling the rest?

A All cells

B Only the first cell

C Last row and last column

D First row and first column

First row and first column are set to 1 because only one path exists to those cells.

Explain how to build the DP table for Unique Paths in a grid.

Think about how you can reach each cell from neighbors.

Describe why dynamic programming is efficient for solving Unique Paths compared to recursion.

Consider what happens if you calculate paths recursively without memory.

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