OmkarPathak · IanDoarn · Oct 24, 2017 · Oct 24, 2017 · Oct 24, 2017 · Oct 24, 2017
diff --git a/pygorithm/dynamic_programming/__init__.py b/pygorithm/dynamic_programming/__init__.py
@@ -3,8 +3,10 @@
 """
 from . import binary_knapsack
 from . import lis
+from . import min_cost_path
 
 __all__ = [
     'binary_knapsack',
-    'lis'
+    'lis',
+    'min_cost_path'
 ]
diff --git a/pygorithm/dynamic_programming/min_cost_path.py b/pygorithm/dynamic_programming/min_cost_path.py
@@ -0,0 +1,51 @@
+"""
+Author: MrDupin
+Created At: 25th August 2017
+"""
+import inspect
+
+#Path(i, j) = min(Path(i-1, j), Path(i, j-1) + Matrix(i, j)
+
+
+def calculate_path(i, j, matrix, s):
+    if(s[i][j] > 0):
+        #We have already calculated solution for i,j; return it.
+        return s[i][j]
+
+    m1 = calculate_path(i-1, j, matrix, s) + matrix[i][j] #Optimal solution for i-1, j (top)
+    m2 = calculate_path(i, j-1, matrix, s) + matrix[i][j] #Optimal solution for i, j-1 (left)
+
+    #Store and return the optimal (minimum) solution
+    if(m1 < m2):
+        s[i][j] = m1
+        return m1
+    else:
+        s[i][j] = m2
+        return m2
+
+
+def find_path(matrix):
+    l = len(matrix);
+    #Initialize solution array.
+    #A node of i, j in solution has an equivalent node of i, j in matrix
+    s = [[0 for i in range(l)] for j in range(l)];
+
+    #Initialize first node as its matrix equivalent
+    s[0][0] = matrix[0][0]
+
+    #Initialize first column as the matrix equivalent + the above solution
+    for i in range(1, l):
+        s[i][0] = matrix[i][0] + s[i-1][0]
+
+    #Initialize first row as the matrix equivalent + the left solution
+    for j in range(1, l):
+        s[0][j] = matrix[0][j] + s[0][j-1]
+
+    return calculate_path(l-1, l-1, matrix, s)
+
+
+def get_code():
+    """
+    returns the code for the min cost path function
+    """
+    return inspect.getsource(calculate_path)
diff --git a/tests/test_dynamic_programming.py b/tests/test_dynamic_programming.py
@@ -3,7 +3,8 @@
 
 from pygorithm.dynamic_programming import (
     binary_knapsack,
-    lis
+    lis,
+    min_cost_path
     )
 
 
@@ -21,5 +22,14 @@ def test_lis(self):
         self.assertEqual(ans[0], 5)
         self.assertEqual(ans[1], [10, 22, 33, 50, 60])
 
+class TestMinCostPath(unittest.TestCase):
+    def test_min_cost_path(self):
+        matrix = [[5, 3, 10, 17, 1],
+                  [4, 2, 9, 8, 5],
+                  [11, 12, 3, 9, 6],
+                  [1, 3, 4, 2, 10],
+                  [7, 11, 13, 7, 3]]
+        self.assertEqual(min_cost_path.find_path(matrix), 38)
+
 if __name__ == '__main__':
     unittest.main()