Why it works
- The paths into a free cell are the paths into the cell above plus the paths into the cell to the left, as without rocks: the last move comes from one of them.
- A rock holds 0, so it adds nothing to the cells after it. That alone removes every path through a rock; no path has to be checked.
- The edges are not all ones any more: along the top row only one straight line leads in, and after a rock it is cut, so (0, 3) gets 0.
Complexity
Time O(m × n): each cell is one check and one addition. Memory O(m × n) for the table, or one row of n cells, since a cell reads only its row and the row above.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗