Combinatoric Solution explained


  • 0
    T

    Let's encode the paths as strings. The following describe valid paths for the 3 × 7 grid:

    DDRRRRRR
    RRRRRRDD
    DRDRDDDD
    ...

    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)))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.