class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
# As moves possible are down and right then we need to calcualte next position value by adding left + up ( as this position can be reached by either from left or from top). You know what we already know up and left value which are nothing but paths to reach them
# go iteratively from start to end by 1 index
if(m == 0 or n == 0):
return 0
if(m == 1 or n == 1):
return 1
memo = [[0]*n for elem in range(m)]
# Assign 1 to first row as there is no up hence it will be 1 only that is from left
for j in range(n):
memo[0][j] = 1
# Assign 1 to first column as there is no left hence it will be 1 only that is from top
for i in range(m):
memo[i][0] = 1
# Now for rest it is just left + top
for i in range(1,m):
for j in range(1,n):
memo[i][j] = memo[i1][j]+memo[i][j1]
# Practically you have calculated maximum paths to reach each and every index
return(memo[1][1])
Python DP solution with comments


It could be further simplified if we set
memo = [[1]*n for _ in xrange(m)]
The complete code is then shrunk toclass Solution: def uniquePaths(self,m,n): memo = [[1]*n for _ in xrange(m)] for i in xrange(1,m): for j in xrange(1,n): memo[i][j] = memo[i1][j]+memo[i][j1] return memo[1][1]
All the test cases passed.