Multi-dimensional DP
What is this?
Sometimes two indices are not enough because the answer also depends on a budget — moves left, time elapsed, or items used. Multi-dimensional DP just adds that budget as one more axis of the table, so a state becomes dp[budget][row][col]. It is the same neighbor-spreading idea as a grid, with a counter ticking down each step, and you still remember every small answer so a given situation is solved only once. Think of a ball bouncing across a grid where you also care about how many moves remain.
💡 Fun fact: Counting problems like these can produce astronomically large totals, so the answer is taken modulo 1,000,000,007 — a prime chosen because it fits in a 32-bit integer and keeps every intermediate multiplication from overflowing.
🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.
Core idea: Sometimes a 2D state isn't enough — the answer also depends on a budget: moves remaining, time elapsed, items used. The fix is to add that quantity as another dimension of the DP, giving
dp[budget][i][j]. The recurrence is the same idea as grid DP, just indexed by one more axis.
Add the axis the problem cares about
![Grid DP dp[r][c] tracks position only; adding a budget gives dp[k][r][c] with k = moves/time/items remaining; the transition spreads to neighbors, decrementing k](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/dynamic-programming/multidimensional-dp/multidimensional-dp-summary-diagram-1.svg)
The cost grows by a factor of the budget's range, but it's usually paid in iterations, not memory (you can roll on the budget axis).
The problem
- Out of Boundary Paths — count ways a ball exits an
m×ngrid withinmaxMovemoves; the state is(moves-left, row, col)and off-grid transitions are exactly what you tally (mod 1e9+7).
Key takeaways
- A budget/time constraint becomes a DP dimension —
dp[k][r][c]. - Same neighbor-spreading recurrence as grid DP, decrementing the budget each step.
- Roll on the budget axis to keep memory at O(m·n).
- Why interviewers love it: it tests whether you can identify all the state a transition truly depends on.
Problem: Out of Boundary Paths.
Out of Boundary Paths
Core idea: Counting paths on a grid is the usual 2D DP — but here the ball has a move budget, and once it runs out, it stops. The number of escape routes from a cell with 3 moves left is different from the number with 1 move left, so the cell alone is not enough state. Add the budget as a third dimension:
dp[k][r][c]= ways to be at(r, c)withkmoves still available. Each step spreads a cell's count to its 4 neighbors; any step that lands off the grid is one escaped path we tally.
Problem, rephrased
Forget the LeetCode phrasing for a second. Here's the scenario:
You're a security analyst watching a roaming patrol drone inside a rectangular m × n warehouse, parcelled into unit cells. The drone starts at cell (startRow, startColumn). Each tick it nudges itself one cell up, down, left, or right. It has a battery good for at most maxMove ticks — it can stop early, but never move more than that. The instant a move would carry it past a wall, it has left the building and the patrol is over.
Count how many distinct move-sequences end with the drone leaving the warehouse, within the budget. The number is astronomically large, so report it modulo 1_000_000_007.
m |
n |
maxMove |
startRow |
startColumn |
Answer | Why |
|---|---|---|---|---|---|---|
| 2 | 2 | 2 | 0 | 0 | 6 | from a corner, 2 ways out in 1 move, more in 2 |
| 1 | 3 | 3 | 0 | 1 | 12 | a thin strip; ball can only go left/right or off |
| 1 | 1 | 0 | 0 | 0 | 0 | no moves allowed → can't leave |
The ball must take a path that crosses the boundary; a sequence that never leaves within the budget simply doesn't count. Two paths are different if their sequences of moves differ, even if they pass through the same cells.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson