Python solution, 7 lines, 1-dim array

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

    Explanation: At each step i, a stores answers for n=i, m=j (in particular, if n=0 or m=0, the answer is always 1). As we increase n by 1, we can apply the recursive formula uniquePaths(m,n)=uniquePaths(m-1,n)+uniquePaths(m,n-1) to find the answer using already computed values. By using a[j]=a[j-1]+a[j] for all j going from 0 up to m-1, we are actually implementing the same formula but within a single one-dimensional array.

Log in to reply

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