5-line python solution

  • 0

    The idea is the same as the standard DP solution. Construct the DP table one row at a time, from left to right.

    class Solution(object):
        def uniquePaths(self, m, n):
            res = [1] * n
            for i in range(m-1):
                for j in range(1, n):
                    res[j] += res[j-1]
            return res[-1]

  • 0

    Good solution!Can you explain more clearly?

  • 0

    As @Mithich said, it's still a DP solution, just in a tricky way.
    Usually we need a mn map to store the result for each step, but here he used only 1n list to make it. In common way, you calculate res[i][j] = res[i-1][j]+res[i][j-1], but in @Mithich solution, res[j] += res[j-1] means res[i..m-1][j] = res[i-1][j]+res[i][j-1].
    Not easy to figure it out clearly, but hope it can help you understand.

  • 0

    @catbaron- Thx a lot for your explanation!

Log in to reply

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