A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
- Right -> Right -> Down
- Right -> Down -> Right
- Down -> Right -> Right Example 2:
Input: m = 7, n = 3 Output: 28
My code:
import numpy as np
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m==0 or n==0:
return 0
if m<=1 or n<=1:
return 1
self.m=m
self.n=n
self.matrix=np.zeros([m,n])-1
#print(self.matrix)
count=self.check_path(1,1)
return int(count)
def check_path(self,i,j):
if i==self.m and j==self.n:
return 0
#print(i==self.m)
if i==self.m:
#print('executing')
return 1
if j==self.n:
return 1
#print(self.m)
#print(i)
#print(j)
if self.matrix[i-1][j-1]!=-1:
#print(self.matrix[i-1][j-1])
#print('call i %d j %d result %d '%(i,j,self.matrix[i-1][j-1]))
return self.matrix[i-1][j-1]
count1=self.check_path(i,j+1)
count2=self.check_path(i+1,j)
self.matrix[i-1][j-1]=count1+count2
#print('i %d j %d result %d count1 %d count2 %d'%(i,j,self.matrix[i-1][j-1],count1,count2))
return self.matrix[i-1][j-1]