How many ways from the top-left to the bottom-right of a 3 x 4 grid, moving only down or right? The state is a cell (r, c): the number of ways to reach it. Fill the table row by row, so whatever a cell needs is already known.
Counting monotone paths on a 3 by 4 grid with a table filled row by row.
(0, 0) is on the top row: the only way in is straight along the edge, so exactly 1 path. A base case, known without any rule.
Cell 0, 0 is a base case with 1 path.
(0, 1) is on the top row: the only way in is straight along the edge, so exactly 1 path. A base case, known without any rule.
Cell 0, 1 is a base case with 1 path.
(0, 2) is on the top row: the only way in is straight along the edge, so exactly 1 path. A base case, known without any rule.
Cell 0, 2 is a base case with 1 path.
(0, 3) is on the top row: the only way in is straight along the edge, so exactly 1 path. A base case, known without any rule.
Cell 0, 3 is a base case with 1 path.
(1, 0) is on the left column: the only way in is straight along the edge, so exactly 1 path. A base case, known without any rule.
Cell 1, 0 is a base case with 1 path.
(1, 1) can be entered from above, 1 way, or from the left, 1 way. Those are disjoint, so 1 + 1 = 2.
Cell 1, 1 is 1 plus 1, which is 2.
(1, 2) can be entered from above, 1 way, or from the left, 2 ways. Those are disjoint, so 1 + 2 = 3.
Cell 1, 2 is 1 plus 2, which is 3.
(1, 3) can be entered from above, 1 way, or from the left, 3 ways. Those are disjoint, so 1 + 3 = 4.
Cell 1, 3 is 1 plus 3, which is 4.
(2, 0) is on the left column: the only way in is straight along the edge, so exactly 1 path. A base case, known without any rule.
Cell 2, 0 is a base case with 1 path.
(2, 1) can be entered from above, 2 ways, or from the left, 1 way. Those are disjoint, so 2 + 1 = 3.
Cell 2, 1 is 2 plus 1, which is 3.
(2, 2) can be entered from above, 3 ways, or from the left, 3 ways. Those are disjoint, so 3 + 3 = 6.
Cell 2, 2 is 3 plus 3, which is 6.
(2, 3) can be entered from above, 4 ways, or from the left, 6 ways. Those are disjoint, so 4 + 6 = 10.
Cell 2, 3 is 4 plus 6, which is 10.
10 paths. Each of the 12 cells was computed once from two known neighbours: O(rows x cols) instead of trying every route. This is Pascal's triangle tilted: the answer is C(5, 2).
There are 10 paths. The table was filled once, cell by cell.