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

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×n grid within maxMove moves; 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.