Given two integers m and n, count the number of paths from the top-left to the bottom-right of an m x n grid when you may move right, down, or diagonally down-right. Pattern focus: Unique paths. Extend the classic recurrence to include the diagonal transition.
m and n are the grid dimensions
number of paths with right, down, and diagonal moves
Example 1:
Input:
m = 2 n = 2
Output:
3
Explanation:
A 2x2 grid has three paths when diagonal moves are allowed.
Example 2:
Input:
m = 3 n = 3
Output:
13
Explanation:
Diagonal moves increase the count to 13 on a 3x3 grid.
Example 3:
Input:
m = 2 n = 3
Output:
5
Explanation:
A 2x3 grid has 5 valid paths with right, down, and diagonal steps.