Minimum Cost Path

netsetos · web-flow · commit bb8d715c65f6 · 2020-06-12T09:41:11.000+05:30
Initial Path
diff --git a/Minimum Cost Path b/Minimum Cost Path
@@ -0,0 +1,33 @@
+# Recursion
+
+def min_cost(cost,m,n):
+    if (n<0 or m<0):
+        return sys.maxsize
+    if (m==0 and n==0):
+        return cost[m][n]
+    else:
+        return cost[m][n]+min(min_cost(cost,m-1,n-1),
+                              min_cost(cost,m-1,n),
+                              min_cost(cost,m,n-1))
+
+
+
+#Dynamic Programming
+
+def min_cost_dp(cost_mat,m,n):
+    dp=[[0 for i in range(m+1)]
+         for j in range(n+1)]
+
+    dp[0][0]=cost_mat[0][0]
+
+    for i in range(1,m+1):
+        dp[i][0]=dp[i-1][0]+cost_mat[i][0]
+    for j in range(1,n+1):
+        dp[0][j]=dp[0][j-1]+cost_mat[0][j]
+
+    for i in range(1,m+1):
+        for j in range(1,n+1):
+            dp[i][j]=cost_mat[i][j]+min(dp[i-1][j-1],
+                                       dp[i-1][j],
+                                       dp[i][j-1])
+    return dp[m][n]
