Grid with obstacles

For the common right-and-down path-counting version, define dp[r][c] as the number of ways to reach cell (r,c). A blocked cell contributes zero and must not inherit paths. Otherwise its value is the sum of the state above and left, with the start set to one only when it is open. Iterating row-major guarantees both dependencies are ready. A one-dimensional array is enough: before overwriting dp[c], it represents paths from above, while dp[c - 1] is the current row’s left value. If the variant minimizes cost instead, use an infinity sentinel for unreachable cells rather than zero. Confirm whether diagonal movement or modulo arithmetic is required. Test blocked start/end, a one-row grid, a one-column grid, all-blocked paths, and integer overflow. The standard solution is O(rows × cols) time and O(cols) space.