Checkpoint Grid Path Count
MediumDynamic Programming ยท Google
Given a grid with n rows and m columns, count the paths from the bottom-left cell to the bottom-right cell. Each move goes one column to the right and either up one row, down one row, or stays in the same row, without leaving the grid.
checkpoints is a list of distinct [row, col] cells, with row 0 at the top. A path counts only if it visits every checkpoint, in the order listed. An empty list counts every path.
Return the number of such paths modulo 1_000_000_007.
Example 1
- Input:
- n = 3, m = 6, checkpoints = [[1, 1], [0, 3]]
- Output:
- 2
- Explanation
- Reaching [1, 1] then [0, 3] leaves two choices for column 2, and column 4 must be row 1 to still reach the bottom-right.
Example 2
- Input:
- n = 3, m = 6, checkpoints = [[0, 3], [1, 1]]
- Output:
- 0
- Explanation
- Column 3 comes after column 1, so no path visits them in this order.
Example 3
- Input:
- n = 3, m = 6, checkpoints = []
- Output:
- 21
Constraints
1 <= n <= 501 <= m <= 10000 <= checkpoints.length <= mcheckpoints[i] = [row, col]with0 <= row < nand0 <= col < m; all checkpoints are distinct