Unique Path_dp

netsetos · web-flow · commit c2935e4c245c · 2020-06-13T10:08:19.000+05:30
Initial File
diff --git a/Unique Path b/Unique Path
@@ -0,0 +1,35 @@
+#Recursive Approach
+
+def path(arr,X,Y):
+      sizeX = len(X)
+      sizeY = len(Y)
+      if(X >= sizeX or Y >= sizeY):
+          return 0
+      elif (arr[X][Y] == 1):
+          return 0
+      elif(X == sizeX-1 and Y == sizeY-1):
+          return 1
+      return self.path(arr, X + 1, Y) + self.path(arr, X, Y + 1)
+      
+
+#Dynamic Programming
+
+def UniquePath(arr):
+    dp=[[0] *len(arr[0])for i in arr]
+    if(arr[0][0]==0):
+        dp[0][0]=1
+
+    for i in range(1,len(arr)):
+        if arr[i][0]==0:
+            dp[i][0]=dp[i-1][0]
+
+    for j in range(1,len(arr[0])):
+        if arr[0][j]==0:
+            dp[0][j]=dp[0][j-1]
+
+    for i in range(1,len(arr)):
+        for j in range(1,len(arr[0])):
+            if arr[i][j]==0:
+                dp[i][j]=dp[i-1][j]+dp[i][j-1]
+
+    return dp[-1][-1]
