Paths With a Diagonal Step
A robot moves from the top-left corner of an m by n grid to the bottom-right corner.
Each move goes RIGHT, DOWN, or DIAGONALLY down-right. Count the distinct paths.
Print the count modulo 1000000007.
3 x 3 -> 13
2 x 2 -> 3 right-down, down-right, or one diagonal
## One more predecessor
Problem 532 allows two moves and sums two predecessors. Adding the diagonal adds a third:
ways[r][c] = ways[r-1][c] + ways[r][c-1] + ways[r-1][c-1]
The three families are disjoint, because a path's LAST move is exactly one of right, down or diagonal. That is the same partition-by-last-move argument as 532, and it is what keeps the sum from double counting.
Worth noting what does NOT change: the diagonal is a single move, not a right followed by a down. Treating it as two moves would make it indistinguishable from a path that is already counted, and the sum would be wrong.
## The rolling row needs care here
In problem 532 a single array worked because ways[r][c] needed the cell above and the cell
to the left, and the in-place update supplied both.
Here it also needs the cell diagonally up-left, which the in-place update has ALREADY overwritten by the time it is read. So either keep two rows, or save the diagonal value in a temporary before overwriting:
prevDiag = dp[c-1] before it was updated this row
Two rows is clearer and the memory is the same order. This is the cheapest kind of bug to introduce by copying the previous problem's loop, and the symptom is an answer too small.
## Boundaries
1 x 5 and 5 x 1 both answer 1: a single row or column leaves no choice, and the diagonal
is never available.
1 x 1 answers 1, the empty path.
2 x 2 answers 3 and 3 x 3 answers 13, both small enough to enumerate by hand and worth
doing once.
## The sequence
These counts are the DELANNOY numbers, and the diagonal of the table runs 1, 3, 13, 63, 321.
4 x 4 answering 63 is a test for that.
There is no simple product formula, unlike the binomial coefficient of problem 532, which is another small reason the table earns its place here.
## Cost
Time O(m n). Space O(n) with two rows.