# Dynamic Programming — Minimum Cost Path Problem

Objec­tive: Given a 2D-matrix where each cell has a cost to travel. You have to write an algo­rithm to find a path from left-top cor­ner to bottom-right cor­ner with min­i­mum travel cost. You can move only right or down.

In the solu­tion we will see that how dynamic pro­gram­ming is much bet­ter approach than recur­sion. Don’t get me wrong, even I like recur­sion a lot 🙂

Exam­ple:

MInimum-Cost-Path-Problem

Approach:

This prob­lem is sim­i­lar to Find all paths from top-left cor­ner to bottom-right cor­ner.

We can solve it using Recur­sion ( return Min(path going right, path going down)) but that won’t be a good solu­tion because we will be solv­ing many sub-problems mul­ti­ple times. Since at every cell we have 2 options the time com­plex­ity will O(2n).

Dynamic Pro­gram­ming:

Cre­ate a solu­tion matrix of the same size as given matrix.

We will fill this matrix in Bottom-up manner.

Given: arrA[][].

```At every cell, we have two options (go right or down) and we will choose the minimum of these two.

So for any i,j cell

solution[i][j] = A[0][j] if i=0 , first row

= A[i][0] if j=0, first column

= A[i][j] + Min(solution[i-1],[j] , solution[i][j-1]) if i>0 && j>0

See the code for better Explanation.
```

Time Com­plex­ity: O(n2).

Code:

```Output:
Minimum Cost Path 29

```

#### You may also like...

• Rahul Shukla

http://www.ideserve.co.in/learn/minimum-cost-path
Here is a nice detailed expla­na­tion of the algorithm.

• Red

I believe the answer is 14, not 29. Can you check? I get that when I run it man­u­ally and with the program.

Also for the fol­low­ing, why are you set­ting 0,0 first rather than set­ting the first row with i=0 to length and first col­umn with i = 0 to length? I think when you do i=1, you are set­ting the val­ues of the sec­ond row and sec­ond col­umn. How can solution[0,i-1] even have a value if you haven’t ini­tial­ized it yet? e.g. for solution[0, 2]

solution[0][0] = A[0][0];
// fill the first row
for (int i = 1; i < A.length; i++) {
solution[0][i] = A[0][i] + solution[0][i — 1];
}

// fill the first col­umn
for (int i = 1; i < A.length; i++) {
solution[i][0] = A[i][0] + solution[i — 1][0];
}

• Red

I tried this and it worked:

pub­lic sta­tic void Min­Cost­Path()
{
int[,] arr = new int[,] { { 1, 7, 9, 2 },
{ 8, 6, 3, 2 },
{ 1, 6, 7, 8 },
{ 2, 9, 8, 2 } };

int[,] solu­tion = new int[arr.GetLength(0), arr.GetLength(1)];

for (int row = 0; row < arr.GetLength(0); row++)
{
solution[row, 0] = arr[row, 0];
}

for (int col = 0; col < arr.GetLength(1); col++)
{
solution[0, col] = arr[0, col];
}

for (int row = 1; row < arr.GetLength(1); row++)
{
for (int col = 1; col < arr.GetLength(0); col++)
{
solution[row, col] = arr[row, col] + Math.Min(solution[row — 1, col], solution[row, col — 1]);
}
}

Console.WriteLine(“Minimum cost of trav­el­ing through the array is: {0}”, solution[solution.GetLength(0)-1, solution.GetLength(1)-1]);
}

• tuto­ri­al­hori­zon

when you say answer is 14, whats the path