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

Recall & Review

beginner

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

Find the number of different 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 state represent in Unique Paths problem?

DP state dp[i][j] represents the number of unique paths to reach cell (i, j) from the start (0, 0).

intermediate

What is the recurrence relation used in Unique Paths DP?

dp[i][j] = dp[i-1][j] + dp[i][j-1], meaning paths to current cell = paths from above + paths from 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).

advanced

How does Unique Paths DP handle obstacles if added to the grid?

Cells with obstacles have dp[i][j] = 0, meaning no paths go through them; other cells sum paths from neighbors if not blocked.

In Unique Paths DP, what does dp[0][0] represent?

A Number of rows

B No paths available

C Starting point with 1 path

D Number of obstacles

dp[0][0] is the start cell, so it has exactly 1 path to itself.

Which moves are allowed in the Unique Paths grid problem?

A Down and Left

B Up and Left

C Up and Right

D Down and Right

Only moves down or right are allowed to reach the bottom-right corner.

What is the time complexity of the Unique Paths DP solution for an m x n grid?

A O(m + n)

B O(m * n)

C O(m^2 * n^2)

D O(1)

We fill an m by n DP table once, so time complexity is O(m * n).

If dp[i][j] = 0 in Unique Paths with obstacles, what does it mean?

A Cell is unreachable or blocked

B Cell has multiple paths

C Cell is the start

D Cell is the destination

Zero paths means the cell is blocked or no way to reach it.

How do you compute dp[i][j] if there are no obstacles?

A dp[i][j] = dp[i-1][j] + dp[i][j-1]

B dp[i][j] = dp[i-1][j] * dp[i][j-1]

C dp[i][j] = max(dp[i-1][j], dp[i][j-1])

D dp[i][j] = dp[i-1][j] - dp[i][j-1]

Paths to current cell are sum of paths from above and left cells.

Explain how to use dynamic programming to find the number of unique paths in a grid.

Think about how paths build from top-left to bottom-right.

Describe how obstacles affect the Unique Paths DP solution and how to handle them.

Obstacles block paths, so no paths go through those cells.