Let's encode the paths as strings. The following describe valid paths for the 3 × 7 grid:
Notice that the order in which the steps are performed doesn't matter, as long as there are 2 steps down and 6 steps to right.
More general, for the m × n problem, any permutation of Dᵐ⁻¹Rⁿ⁻¹ is a valid path. The solution is therefore the number of unique permutations of Dᵐ⁻¹Rⁿ⁻¹.
In a first step, let's ignore the uniqueness:
For m-1+n-1 elements, the number of permutations is
(m-1+n-1)! = (m+n-2)!
Now let's account for uniqueness:
There are (m-1)! ways to order the Ds, and (n-1)! ways to order the Rs in any permutation. This means, that the above figure includes (m-1)!*(n-1)! duplicates of each unique permutation. The number of unique permutations therefore is:
(m+n-2)! / ( (m-1)! *(n-1)! )
Here the Python code:
class Solution: def uniquePaths(self, m, n): return int(math.factorial(m+n-2) / (math.factorial(m-1)*math.factorial(n-1)))