Navigate 2D grids with DP for unique paths, minimum path sum, and dungeon problems.
Grid DP uses a 2D dp table where dp[i][j] represents the answer for the cell at row i, column j. The recurrence typically combines dp[i-1][j] (from above) and dp[i][j-1] (from left).
O(m × n)
O(m × n) reducible to O(n)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
set dp[i][j] = 0 or Infinity if cell is blocked
use a 1D rolling array instead of full 2D table
sometimes right/down/left/up are all valid
harder variants requiring max/min tracking