Question Bank
DP on Grids Quiz
Difficulty: Medium
Path counts, minimum path sum, and obstacle handling on rectangular grids. Code stems are Python.
DP on Grids Quiz
Path counts, minimum path sum, and obstacle handling on rectangular grids. Code stems are Python.
660 views
14
Implement unique_paths(m, n): count paths from the top-left to bottom-right of an m x n grid moving only right or down.
Examples
Example 1:
Input: m = 3, n = 7
Output: 28
Explanation: dp[r][c] = dp[r - 1][c] + dp[r][c - 1] with the first row and column all 1. Closed form C(m + n - 2, m - 1) = C(8, 2) = 28.Implement min_path_sum(grid): starting at (0, 0), end at (R - 1, C - 1), moves are right or down, minimize sum of visited cells.
Examples
Example 1:
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Explanation: In-place DP grid[r][c] += min(grid[r - 1][c], grid[r][c - 1]). Optimal path 1 -> 3 -> 1 -> 1 -> 1 sums to 7. The greedy 'pick smaller neighbor' is unsafe; DP correctly trades off local cost for downstream savings.Path count with obstacles: grid[r][c] = 1 blocks a cell. Implement unique_paths_obstacles(grid).
Examples
Example 1:
Input: grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2
Explanation: Same recurrence, but set dp[r][c] = 0 whenever the cell is blocked. Two paths skirt the central obstacle: right-right-down-down and down-down-right-right.Why can you process a right/down grid DP in row-major order without needing any explicit topological sort?
Reduce the unique_paths(m, n) space from O(m * n) to O(min(m, n)) and explain why the rolling-row trick is safe.