Why it works
- Every path into (r, c) makes its last move either down from (r - 1, c) or right from (r, c - 1). No path does both, so the paths into a cell are exactly the paths into those two cells, added up.
- A cell of the top row or the left column has only one way in, a straight line from the start, so it holds 1. These cells start the table.
- Row by row, left to right, both cells a cell reads are filled before it, so every cell is computed once from finished numbers.
Complexity
Time O(m × n): each cell is one addition. Memory O(m × n) for the table; a cell reads only its own row and the row above, so one row of n cells is enough.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗