Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

2-D dynamic programming

Grid DP

dp[r][c] from neighbours; add a dimension for extra state (jumps left).

Visual guide Quiz (9) Spot the pattern

Notes

Recognise it when: paths through a grid with right/down moves and max or min or count.

dp[r][c] = grid[r][c] + best(dp[r-1][c], dp[r][c-1])

Extra constraints get extra dimensions: dp[r][c][j] = best score having used j jumps (or keys, or skips). Transitions: normal moves keep j; special moves go from j-1.

Gotchas

Initialize unreachable states to -inf, not 0, especially with negative cells.
The answer is max over all j, because using the extra moves is optional.

6 problems

Interview roadmap

2-D dynamic programming Grids, two strings, knapsacks, ranges.

Grid DP guide

Basics: Count grid paths around obstacles basics easy
Mushroom walks with an exact haul easy
Minimum Path Sum py · c++ · java easy
Max-score grid path with limited jumps 4 levels OpenAI hard
Robots matching a sensor reading Uber py · c++ · java medium
Longest Increasing Path in a Matrix py · c++ · java hard