Dynamic Programming21 sections · 916 units
Open in Course

Grid Paths - Problem Statement

Counting paths in a grid

You have an nn×nn grid. You start at the top-left corner and need to reach the bottom-right corner. You can only move right or down. Some cells are blocked (marked with '*'), and you cannot step on them. Count the number of paths from start to finish. Since the answer can be huge, return it modulo 10910^9 + 7.

This is Grid 1 from AtCoder, but with a twist: you need to handle blocked cells. Before reading the solution, think about how you would modify the basic grid DP to skip obstacles.