A robot sits at the top-left of an m×n grid and can move only right or down. How many distinct paths reach the bottom-right corner? e.g. 3×7 → 28.
Recognising a grid-counting DP where each cell's path count is the SUM of the ways to reach the cells feeding into it.
Counting paths on a grid is the canonical additive 2D DP: dp[i][j] = number of ways to reach cell (i,j). Because moves are only right/down, the only predecessors are the cell above and the cell to the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. The first row and first column are all 1 (a single straight-line path). Answer is dp[m-1][n-1]. It collapses to one rolling row for O(n) space, and there is even a closed form C(m+n-2, m-1) since a path is just a choice of which of the m+n-2 steps go down. Recognition signal: 'count the number of ways to reach X' with local moves → additive DP summing the reachable predecessors (contrast min/max path DP, which takes the BEST predecessor, not the sum). Obstacles simply force those cells to 0.
Counting paths/ways to reach a target under local move rules → dp[cell] = sum of dp[predecessors]; switch sum→max/min when you need best-cost paths instead of counts.
Time O(m·n) · Space O(n) with a rolling row