Python dp top down approach O(m*n) complexicity


#1

class Solution:
# @param A : list of list of integers
# @return an integer
def init(self):
self.dp = {}
def function(self,A):
if A[0][0] == 1:
return 0
def recursive(A,i,j):
if (i,j) in self.dp:
return self.dp[(i,j)]
if i == 0 and j == 0:
if A[i][j] == 1:
self.dp[(i,j)] = 0
return 0
else :
self.dp[(i,j)] = 1
return 1
elif i == 0 :
if A[i][j] == 1:
self.dp[(i,j)] = 0
return 0
else :
t = recursive(A,i,j-1)
self.dp[(i,j)] = t
return t
elif j == 0:
if A[i][j] == 1:
self.dp[(i,j)] = 0
return 0
else :
t = recursive(A,i-1,j)
self.dp[(i,j)] = t
return t
else :
if A[i][j] == 1 :
self.dp[(i,j)] = 0
return 0
else :
t = recursive(A,i-1,j) + recursive(A,i,j-1)
self.dp[(i,j)] = t
return t
recursive(A,len(A)-1,len(A[0])-1)
return self.dp[(len(A)-1,len(A[0])-1)]
def uniquePathsWithObstacles(self, A):
return self.function(A)

> indent preformatted text by 4 spaces