Unique Paths

2D dynamic programming · Build a grid from top and left · Easy · about 23 min

Why it matters

A 2D state is only a grid of small questions, not a new kind of magic.

How it connects

Dynamic programming can live on a grid too: every cell combines answers from nearby cells.

Try first

How can you arrive at an ordinary cell if movement is only right or down?

Interview cue

The state is paths to a cell; each transition uses the two ways that can enter it.