One line in Python

  • 4

    It's true that this can be solved with dynamic programming. But you can see that every path has exactly m - 1 horizontal moves and n - 1 vertical moves. So, to get a particular path, you need to choose where to put your m - 1 horizontal moves (or your n - 1 vertical moves) amongst the m + n - 2 total moves. That gives (m+n-2 choose m-1) paths (or (m+n-2 choose n-1), which is the same).

    class Solution:
        # @return an integer
        def uniquePaths(self, m, n):
            return math.factorial(m + n - 2) / (math.factorial(m - 1) * math.factorial(n - 1))

  • 0

    The solution is mathematically correct as this is just a lattice paths problem which is defined by the binomial coefficient (m+n choose n). However, the problem defined that m and n could be as large as 100 and 100! easily overflows a 64 bit long.

  • 0

    In Python, integers are not limited by 64bits, unless I'm mistaken. It allows arbitrarily large integers, which is why this solution works while the same formula wouldn't work in C++ or Java (unless you used BigInteger).

Log in to reply

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