DSA: Dynamic Programming on Grids and Matrices
Solve path counting, minimum cost, and interval DP problems on 2D grids and matrix chains.
Unique Paths in a Grid
Count distinct paths from the top-left to the bottom-right of anm×n grid moving only right or down.
Unique Paths
dp[i][j] = number of ways to reach cell (i, j) from (0, 0).
- Base: entire first row and first column = 1 (only one direction available)
- Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]
- Combinatorial formula: C(m+n-2, m-1) gives same answer
- Time: O(m * n), Space: O(m * n) or O(n) with 1D optimization
Unique Paths
C++Initialize borders to 1; fill interior with sum of top and left neighbors.
Unique Paths with Obstacles
Same as Unique Paths but cells marked 1 are blocked. Set dp[i][j] = 0 for obstacle cells since no path can pass through them.
Unique Paths with Obstacles
Obstacle cell forces dp[i][j] = 0, blocking all paths that would pass through it.
- If grid[i][j] == 1: dp[i][j] = 0
- If grid[i][j] == 0: dp[i][j] = dp[i-1][j] + dp[i][j-1] as normal
- Border cells with obstacles also become 0, cutting off entire rows/columns
- If start or end cell is blocked, answer is 0
Unique Paths with Obstacles
C++Obstacle cells set to 0; border initialization stops at first obstacle.
Minimum Path Sum
Find the path from top-left to bottom-right (moving only right or down) that minimizes the sum of all cell values along the path.
Minimum Path Sum
dp[i][j] = minimum cost to reach cell (i, j) from (0, 0).
- Base: dp[0][0] = grid[0][0]
- First row: dp[0][j] = dp[0][j-1] + grid[0][j] (can only come from left)
- First col: dp[i][0] = dp[i-1][0] + grid[i][0] (can only come from above)
- Recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Minimum Path Sum
C++Add grid value to the minimum of the top and left neighbors.
Triangle Minimum Path
Given a triangle of numbers, find the minimum path sum from the top to the bottom row. From each cell (i, j) you can move to(i+1, j) or(i+1, j+1).
Triangle Minimum Path
Fill bottom-up: start from last row, work upward. No extra space needed (modify in place).
- Start with dp = last row of triangle
- For each row above: dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
- After processing row 0, dp[0] holds the answer
- Bottom-up avoids needing to track path endpoints separately
Triangle Minimum Path
C++Bottom-up in-place DP: propagate minimum costs up to the apex.
Dungeon Game
A knight starts at top-left and must reach bottom-right. Each cell adds or subtracts health. Find the minimum initial health needed so the knight never drops to 0 or below.
Dungeon Game
Fill dp from bottom-right to top-left: dp[i][j] = minimum health needed upon entering cell (i, j).
- dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
- Max with 1: health can never be 0 or negative
- Subtract dungeon[i][j]: positive cell reduces required health; negative increases it
- Base: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
Dungeon Game
C++Reverse fill: minimum health entering each cell depends on what lies ahead.
Egg Dropping Puzzle
Given e eggs andf floors, find the minimum number of trials in the worst case to determine the critical floor (highest floor from which an egg does not break).
Egg Drop
dp[i][j] = min trials with i eggs and j floors.
- Base: dp[1][j] = j (one egg: must try every floor linearly)
- Base: dp[i][0] = 0, dp[i][1] = 1
- For each floor k tried: worst case = 1 + max(egg breaks: dp[i-1][k-1], survives: dp[i][j-k])
- Recurrence: dp[i][j] = min over all k of (1 + max(dp[i-1][k-1], dp[i][j-k]))
- Time: O(e * f²); optimizable to O(e * f * log f) with binary search
Egg Dropping Puzzle
C++Try every floor k; take worst case of break/survive; minimize over all k.
Matrix Chain Multiplication
Given a chain of matrices, find the optimal parenthesization that minimizes the total number of scalar multiplications. This is an interval DP problem.
Matrix Chain Multiplication
dp[i][j] = min scalar multiplications to compute product of matrices i through j.
- Dimensions stored as array p[]: matrix i has size p[i-1] x p[i]
- Split at k: cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
- Recurrence: dp[i][j] = min over k in [i, j-1] of (split cost)
- Fill by increasing chain length (len = 2 to n)
- Time: O(n³), Space: O(n²)
Matrix Chain Multiplication
C++Interval DP: fill by chain length, try every split point k.
Burst Balloons
Given balloons with values, bursting balloon k earnsnums[left] * nums[k] * nums[right] coins where left and right are the nearest un-burst neighbors. Maximize total coins.
Burst Balloons
Think of k as the LAST balloon burst in range [i, j]. Boundaries i-1 and j+1 are guaranteed present.
- Pad array with 1s at both ends to simplify boundary handling
- dp[i][j] = max coins from bursting all balloons strictly between i and j
- For last burst k: coins = nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j]
- Fill by increasing interval length
- Time: O(n³), Space: O(n²)
Burst Balloons
C++Treat k as the last balloon burst; left and right boundaries remain intact.
Grid and Matrix DP Problem Map
These problems split into two families: grid path problems (fill top-left to bottom-right or reverse) and interval DP problems (fill by increasing length).
| Problem | DP Family | Fill Direction | Time |
|---|---|---|---|
| Unique Paths | Grid path count | Top-left to bottom-right | O(m*n) |
| Unique Paths + Obstacles | Grid path count | Top-left to bottom-right | O(m*n) |
| Min Path Sum | Grid path cost | Top-left to bottom-right | O(m*n) |
| Triangle Min Path | Grid path cost | Bottom-up rows | O(n²) |
| Dungeon Game | Grid path cost | Bottom-right to top-left | O(m*n) |
| Egg Drop | Decision DP | By floors and eggs | O(e*f²) |
| Matrix Chain Mult | Interval DP | By chain length | O(n³) |
| Burst Balloons | Interval DP | By interval length | O(n³) |
Knowledge Check
1. In the Unique Paths problem (m×n grid, only right or down), how many paths exist?
2. How does an obstacle affect the Unique Paths DP?
3. Minimum Path Sum recurrence for moving only right or down is:
4. In the Triangle Minimum Path problem, what is the recurrence for bottom-up DP?
5. The Dungeon Game DP is filled from bottom-right to top-left because:
6. Matrix Chain Multiplication dp[i][j] represents:
7. In the Egg Drop problem with 1 egg and k floors, the minimum trials needed is:
8. Burst Balloons dp[i][j] represents: