DP on Grids Quiz
Path counts, minimum path sum, and obstacle handling on rectangular grids. Code stems are Python.
Question Bank
Medium
Python
5 questions
grid-dp
dynamic-programming
algorithms
quiz
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.def unique_paths(m, n):
# TODO
passImplement 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.def min_path_sum(grid):
# TODO
passPath 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.def unique_paths_obstacles(grid):
# TODO
passWhy 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.