Dynamic Programming

Grid Path Count Table

Count right-and-down grid paths by adding top and left cells. This is a small deterministic dynamic-programming example.

Example

Count right-and-down grid paths by adding top and left cells.

highlighted = computed this step

Step 1 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((0, 0), (start), 1)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((0, 0), (start), 1)}}\end{array}

Step 2 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((0, 1), ((0, 0), 1), 1)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((0, 1), ((0, 0), 1), 1)}}\end{array}

Step 3 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((0, 2), ((0, 1), 1), 1)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((0, 2), ((0, 1), 1), 1)}}\end{array}

Step 4 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((1, 0), ((0, 0), 1), 1)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((1, 0), ((0, 0), 1), 1)}}\end{array}

Step 5 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((1, 1), ((0, 1), 1, (1, 0), 1), 2)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((1, 1), ((0, 1), 1, (1, 0), 1), 2)}}\end{array}

Step 6 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((1, 2), ((0, 2), 1, (1, 1), 2), 3)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((1, 2), ((0, 2), 1, (1, 1), 2), 3)}}\end{array}

Step 7 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((2, 0), ((1, 0), 1), 1)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((2, 0), ((1, 0), 1), 1)}}\end{array}

Step 8 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((2, 1), ((1, 1), 2, (2, 0), 1), 3)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((2, 1), ((1, 1), 2, (2, 0), 1), 3)}}\end{array}

Step 9 — Grid cell

Compute the highlighted combinatorics value.

cell, inputs, paths((2, 2), ((1, 2), 3, (2, 1), 3), 6)\begin{array}{c|c}\text{cell, inputs, paths}&\hlmath{\text{((2, 2), ((1, 2), 3, (2, 1), 3), 6)}}\end{array}
combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.