Dynamic programming 0/49

Knapsack DP: capacity tables and grid paths · 1 of 2

Grid DP

Count the paths through a grid, find the cheapest path and the largest square of 1s, with one state per cell and a transition from the neighbouring cells.

3,023 words · 14 min read

Part 1 of 7 Paths in a grid

Paths in a grid

In the frog, stairs and coin problems, every state was a position in a row: a stone, a step, an amount of money. In this lesson the input is a grid, and each state is one of its cells. The problems are about paths. A path starts in the top-left cell, moves one cell to the right or one cell down at each step, and ends in the bottom-right cell. The first problem asks how many paths there are.

Difficulty tier:Very Easy

A robot stands in the top-left cell of a grid with mm rows and nn columns and wants to reach the bottom-right cell. Each move takes it one cell right or one cell down.

Return the number of different paths the robot can take.

Constraints

  • 1≤m,n≤1001 \le m, n \le 100
  • The answer is at most 2⋅1092 \cdot 10^9

Sample 1 · Input

m = 3, n = 7

Output

28

Sample 2 · Input

m = 3, n = 2

Output

3

In the second sample the grid has 3 rows and 2 columns. Every path makes two moves down and one move right, and the three paths differ only in when the move right happens:

  • right, down, down
  • down, right, down
  • down, down, right

A program could count the paths by generating them one at a time, but there are too many. In a grid with mm rows and nn columns, every path makes m−1m - 1 moves down and n−1n - 1 moves right, so a path is fixed once we say which of its moves go down. A grid of 17 rows and 17 columns, well inside the limits, has 32 moves on every path, and there are 601,080,390 ways to choose the 16 that go down. Instead, we compute one number for each cell, the number of paths that reach it, and that grid has only 17×17=28917 \times 17 = 289 cells.

For this problem the choice of moves also gives a formula, (m+n−2m−1)\binom{m + n - 2}{m - 1}. The cell-by-cell method gives the same numbers, and unlike the formula it still works later in the lesson, when some cells are blocked.