Grid DP
dp[r][c] depends on the cells you can arrive from, usually up and left. Walk the grid in dependency order.
Dynamic ProgrammingO(rows * cols)New13 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
unique paths
minimum path sum
maximal square
dungeon game
The template
Get this into muscle memory, then adapt the condition per problem.
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
dp[r][c] = grid[r][c] + Math.min(r ? dp[r-1][c] : INF, c ? dp[r][c-1] : INF); Watch Minimum Path SumIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Movement is restricted, which fixes the dependency direction.
- 2Initialise the first row and column separately.
- 3Some variants must be filled from the bottom right backwards.
Drill it
Every problem in the bank that uses this pattern.
0 / 13 solved