Core pattern
Grid DP
Step 5 of 14Pattern 3 of 7
×How to recognize it fast
Grid DP shows up when movement is constrained and every cell depends on one or more neighboring cells.
When you see
matrixmove right / downpath sumunique pathsfalling path
Think
- Each cell depends on answers from nearby cells.
- The state is almost always dp[row][col].
What to do once the pattern is clear
Core trick
- Define dp[r][c] as the answer at this cell.
- Set clean boundary conditions for the first row and first column.
- If forward transitions feel awkward, try filling the table backward.
Shortcut recognition
Grid plus movement constraintsRight / down or top / left dependenciesPath count or path cost
Hidden trick
Backward DP often makes messy grid questions much cleaner. Dungeon Game and Triangle both become easier when you solve from the destination backward.
Unique Paths recurrence
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]