Posted on by Kalkicode
Code Dynamic Programming

# Min cost path in matrix

The min cost path problem involves finding the path with the minimum cost from the top-left corner of a matrix to the bottom-right corner. Each cell in the matrix represents the cost to traverse that cell. The goal is to find the path that minimizes the total cost of traversal.

## Problem Statement

Given a matrix of size R x C, where each cell represents the cost to traverse that cell, the objective is to find the minimum cost path from the top-left corner to the bottom-right corner. The path can only move down, right, or diagonally (down-right).

## Pseudocode Algorithm

Let's present a pseudocode algorithm to solve the min cost path problem:

```minCost(data):
Create a 2D array dp of size R x C

Set dp[0][0] to data[0][0] (initialize the starting point)

// Set the first column of dp
for i = 1 to R-1:
dp[i][0] = data[i][0] + dp[i-1][0]

// Set the first row of dp
for j = 1 to C-1:
dp[0][j] = data[0][j] + dp[0][j-1]

// Fill the rest of dp
for i = 1 to R-1:
for j = 1 to C-1:
dp[i][j] = data[i][j] + min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])

Print "Min Cost: " + dp[R-1][C-1]
```

The above algorithm uses dynamic programming to calculate the minimum cost at each cell of the dp matrix. It starts by initializing the first row and the first column of dp. Then, it iterates through the remaining cells, calculating the minimum cost based on the previous cells' values and the current cell's cost.

## Code Solution

``````// C Program
// Min cost path in matrix
#include <stdio.h>

#define R 4
#define C 5
// Returns the minimum of a given three values
int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
void minCost(int data[R][C])
{
// Auxiliary space which are used to find min path
int dp[R][C];
// Set first point
dp[0][0] = data[0][0];
// Loop controlling variables
int i = 0;
int j = 0;
// Set first column
for (i = 1; i < R; ++i)
{
dp[i][0] = data[i][0] + dp[i - 1][0];
}
// Set first row
for (i = 1; i < C; ++i)
{
dp[0][i] = data[0][i] + dp[0][i - 1];
}
// iterate the loop through by row
for (i = 1; i < R; ++i)
{
// iterate the loop through by column
for (j = 1; j < C; ++j)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i][j] = data[i][j] + minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
}
}
// Display calculated result
printf("\n Min Cost : %d", dp[R - 1][C - 1]);
}
int main()
{
int data[R][C] = {
{
1 , 3 , 1 , 2 , 3
},
{
2 , 1 , 1 , 2 , 8
},
{
1 , 2 , 8 , 7 , 3
},
{
1 , 2 , 3 , 2 , 5
}
};
minCost(data);
return 0;
}``````

#### Output

`` Min Cost : 13``
``````/*
Java Program
Min cost path in matrix
*/
public class Cost{
// Returns the minimum of a given three values
public int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
public void minCost(int[][] data, int r, int c)
{
// Auxiliary space which are used to find min path
int[][] dp = new int[r][c];
// Set first point
dp[0][0] = data[0][0];
// Loop controlling variables
int i = 0;
int j = 0;
// Set first column
for (i = 1; i < r; ++i)
{
dp[i][0] = data[i][0] + dp[i - 1][0];
}
// Set first row
for (i = 1; i < c; ++i)
{
dp[0][i] = data[0][i] + dp[0][i - 1];
}
// iterate the loop through by row
for (i = 1; i < r; ++i)
{
// iterate the loop through by column
for (j = 1; j < c; ++j)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i][j] = data[i][j] + minValue(dp[i - 1][j],
dp[i - 1][j - 1],
dp[i][j - 1]);
}
}
// Display calculated result
System.out.print("\n Min Cost : " + dp[r - 1][c - 1]);
}
public static void main(String[] args)
{

int[][] data =
{
{
1 , 3 , 1 , 2 , 3
} ,
{
2 , 1 , 1 , 2 , 8
} ,
{
1 , 2 , 8 , 7 , 3
} ,
{
1 , 2 , 3 , 2 , 5
}
};
int r = data.length;
int c = data[0].length;
}
}``````

#### Output

`` Min Cost : 13``
``````// Include header file
#include <iostream>
#define R 4
#define C 5
using namespace std;
/*
C++ Program
Min cost path in matrix
*/
class Cost
{
public:
// Returns the minimum of a given three values
int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
void minCost(int data[R][C])
{
// Auxiliary space which are used to find min path
int dp[R][C];
// Set first point
dp[0][0] = data[0][0];
// Loop controlling variables
int i = 0;
int j = 0;
// Set first column
for (i = 1; i < R; ++i)
{
dp[i][0] = data[i][0] + dp[i - 1][0];
}
// Set first row
for (i = 1; i < C; ++i)
{
dp[0][i] = data[0][i] + dp[0][i - 1];
}
// iterate the loop through by row
for (i = 1; i < R; ++i)
{
// iterate the loop through by column
for (j = 1; j < C; ++j)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i][j] = data[i][j] + this->minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
}
}
// Display calculated result
cout << "\n Min Cost : " << dp[R - 1][C - 1];
}
};
int main()
{
int data[R][C] = {
{
1 , 3 , 1 , 2 , 3
} , {
2 , 1 , 1 , 2 , 8
} , {
1 , 2 , 8 , 7 , 3
} , {
1 , 2 , 3 , 2 , 5
}
};

return 0;
}``````

#### Output

`` Min Cost : 13``
``````// Include namespace system
using System;
/*
C# Program
Min cost path in matrix
*/
public class Cost
{
// Returns the minimum of a given three values
public int minValue(int a, int b, int c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
public void minCost(int[,] data, int r, int c)
{
// Auxiliary space which are used to find min path
int[,] dp = new int[r,c];
// Set first point
dp[0,0] = data[0,0];
// Loop controlling variables
int i = 0;
int j = 0;
// Set first column
for (i = 1; i < r; ++i)
{
dp[i,0] = data[i,0] + dp[i - 1,0];
}
// Set first row
for (i = 1; i < c; ++i)
{
dp[0,i] = data[0,i] + dp[0,i - 1];
}
// iterate the loop through by row
for (i = 1; i < r; ++i)
{
// iterate the loop through by column
for (j = 1; j < c; ++j)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i,j] = data[i,j] + minValue(
dp[i - 1,j], dp[i - 1,j - 1], dp[i,j - 1]);
}
}
// Display calculated result
Console.Write("\n Min Cost : " + dp[r - 1,c - 1]);
}
public static void Main(String[] args)
{
int[,] data = {
{
1 , 3 , 1 , 2 , 3
} , {
2 , 1 , 1 , 2 , 8
} , {
1 , 2 , 8 , 7 , 3
} , {
1 , 2 , 3 , 2 , 5
}
};
// Get number of row and column
int r = data.GetLength(0);
int c = data.GetLength(1);
}
}``````

#### Output

`` Min Cost : 13``
``````<?php
/*
Php Program
Min cost path in matrix
*/
class Cost
{
// Returns the minimum of a given three values
public	function minValue(\$a, \$b, \$c)
{
if (\$a > \$b)
{
if (\$b > \$c)
{
return \$c;
}
else
{
return \$b;
}
}
else
{
if (\$a > \$c)
{
return \$c;
}
else
{
return \$a;
}
}
}
// Find minimum cost path in given data matrix
public	function minCost( & \$data, \$r, \$c)
{
// Auxiliary space which are used to find min path
\$dp = array_fill(0, \$r, array_fill(0, \$c, 0));
// Set first point
\$dp[0][0] = \$data[0][0];
// Loop controlling variables
\$i = 0;
\$j = 0;
// Set first column
for (\$i = 1; \$i < \$r; ++\$i)
{
\$dp[\$i][0] = \$data[\$i][0] + \$dp[\$i - 1][0];
}
// Set first row
for (\$i = 1; \$i < \$c; ++\$i)
{
\$dp[0][\$i] = \$data[0][\$i] + \$dp[0][\$i - 1];
}
// iterate the loop through by row
for (\$i = 1; \$i < \$r; ++\$i)
{
// iterate the loop through by column
for (\$j = 1; \$j < \$c; ++\$j)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
\$dp[\$i][\$j] = \$data[\$i][\$j] + \$this->minValue(\$dp[\$i - 1][\$j], \$dp[\$i - 1][\$j - 1], \$dp[\$i][\$j - 1]);
}
}
// Display calculated result
echo "\n Min Cost : ". \$dp[\$r - 1][\$c - 1];
}
}

function main()
{
\$data = array(
array(1, 3, 1, 2, 3),
array(2, 1, 1, 2, 8),
array(1, 2, 8, 7, 3),
array(1, 2, 3, 2, 5)
);
// Get number of row and column
\$r = count(\$data);
\$c = count(\$data[0]);
}
main();``````

#### Output

`` Min Cost : 13``
``````/*
Node Js Program
Min cost path in matrix
*/
class Cost
{
// Returns the minimum of a given three values
minValue(a, b, c)
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
minCost(data, r, c)
{
// Auxiliary space which are used to find min path
var dp = Array(r).fill(0).map(() => new Array(c).fill(0));
// Set first point
dp[0][0] = data[0][0];
// Loop controlling variables
var i = 0;
var j = 0;
// Set first column
for (i = 1; i < r; ++i)
{
dp[i][0] = data[i][0] + dp[i - 1][0];
}
// Set first row
for (i = 1; i < c; ++i)
{
dp[0][i] = data[0][i] + dp[0][i - 1];
}
// iterate the loop through by row
for (i = 1; i < r; ++i)
{
// iterate the loop through by column
for (j = 1; j < c; ++j)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i][j] = data[i][j] + this.minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
);
}
}
// Display calculated result
process.stdout.write("\n Min Cost : " + dp[r - 1][c - 1]);
}
}

function main()
{
var data = [
[1, 3, 1, 2, 3] ,
[2, 1, 1, 2, 8] ,
[1, 2, 8, 7, 3] ,
[1, 2, 3, 2, 5]
];
// Get number of row and column
var r = data.length;
var c = data[0].length;
}
main();``````

#### Output

`` Min Cost : 13``
``````#   Python 3 Program
#   Min cost path in matrix

class Cost :
#  Returns the minimum of a given three values
def minValue(self, a, b, c) :
if (a > b) :
if (b > c) :
return c
else :
return b

else :
if (a > c) :
return c
else :
return a

#  Find minimum cost path in given data matrix
def minCost(self, data, r, c) :
#  Auxiliary space which are used to find min path
dp = [[0] * (c) for _ in range(r) ]
#  Set first point
dp[0][0] = data[0][0]
#  Loop controlling variables
i = 1
j = 1
#  Set first column
while (i < r) :
dp[i][0] = data[i][0] + dp[i - 1][0]
i += 1

i = 1
#  Set first row
while (i < c) :
dp[0][i] = data[0][i] + dp[0][i - 1]
i += 1

i = 1
#  iterate the loop through by row
while (i < r) :
#  iterate the loop through by column
while (j < c) :
#  minValue(top, top left, and left element)
#   b   a
#     ↖ ↑
#   c ← x
dp[i][j] = data[i][j] + self.minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
j += 1

i += 1
j = 1

#  Display calculated result
print("\n Min Cost : ", dp[r - 1][c - 1], end = "")

def main() :
data = [
[1, 3, 1, 2, 3] ,
[2, 1, 1, 2, 8] ,
[1, 2, 8, 7, 3] ,
[1, 2, 3, 2, 5]
]
#  Get number of row and column
r = len(data)
c = len(data[0])

if __name__ == "__main__": main()``````

#### Output

`` Min Cost :  13``
``````#   Ruby Program
#   Min cost path in matrix

class Cost
#  Returns the minimum of a given three values
def minValue(a, b, c)
if (a > b)
if (b > c)
return c
else
return b
end

else
if (a > c)
return c
else
return a
end

end

end

#  Find minimum cost path in given data matrix
def minCost(data, r, c)
#  Auxiliary space which are used to find min path
dp = Array.new(r) {Array.new(c) {0}}
#  Set first point
dp[0][0] = data[0][0]
#  Loop controlling variables
i = 1
j = 1
#  Set first column
while (i < r)
dp[i][0] = data[i][0] + dp[i - 1][0]
i += 1
end

i = 1
#  Set first row
while (i < c)
dp[0][i] = data[0][i] + dp[0][i - 1]
i += 1
end

i = 1
#  iterate the loop through by row
while (i < r)
#  iterate the loop through by column
while (j < c)
#  minValue(top, top left, and left element)
#   b   a
#     ↖ ↑
#   c ← x
dp[i][j] = data[i][j] + self.minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
)
j += 1
end

i += 1
j = 1
end

#  Display calculated result
print("\n Min Cost : ", dp[r - 1][c - 1])
end

end

def main()
data = [
[1, 3, 1, 2, 3] ,
[2, 1, 1, 2, 8] ,
[1, 2, 8, 7, 3] ,
[1, 2, 3, 2, 5]
]
#  Get number of row and column
r = data.length
c = data[0].length
end

main()``````

#### Output

`` Min Cost : 13``
``````/*
Scala Program
Min cost path in matrix
*/
class Cost
{
// Returns the minimum of a given three values
def minValue(a: Int, b: Int, c: Int): Int = {
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
def minCost(data: Array[Array[Int]], r: Int, c: Int): Unit = {
// Auxiliary space which are used to find min path
var dp: Array[Array[Int]] = Array.fill[Int](r, c)(0);
// Set first point
dp(0)(0) = data(0)(0);
// Loop controlling variables
var i: Int = 1;
var j: Int = 1;
// Set first column
while (i < r)
{
dp(i)(0) = data(i)(0) + dp(i - 1)(0);
i += 1;
}
i = 1;
// Set first row
while (i < c)
{
dp(0)(i) = data(0)(i) + dp(0)(i - 1);
i += 1;
}
i = 1;
// iterate the loop through by row
while (i < r)
{
// iterate the loop through by column
while (j < c)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp(i)(j) = data(i)(j) + this.minValue(
dp(i - 1)(j), dp(i - 1)(j - 1), dp(i)(j - 1)
);
j += 1;
}
i += 1;
j = 1;
}
// Display calculated result
print("\n Min Cost : " + dp(r - 1)(c - 1));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Cost = new Cost();
var data: Array[Array[Int]] = Array(
Array(1, 3, 1, 2, 3),
Array(2, 1, 1, 2, 8),
Array(1, 2, 8, 7, 3),
Array(1, 2, 3, 2, 5)
);
// Get number of row and column
var r: Int = data.length;
var c: Int = data(0).length;
}
}``````

#### Output

`` Min Cost : 13``
``````/*
Swift 4 Program
Min cost path in matrix
*/
class Cost
{
// Returns the minimum of a given three values
func minValue(_ a: Int, _ b: Int, _ c: Int)->Int
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
func minCost(_ data: [[Int]], _ r: Int, _ c: Int)
{
// Auxiliary space which are used to find min path
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: c), count: r);
// Set first point
dp[0][0] = data[0][0];
// Loop controlling variables
var i: Int = 1;
var j: Int = 1;
// Set first column
while (i < r)
{
dp[i][0] = data[i][0] + dp[i - 1][0];
i += 1;
}
i = 1;
// Set first row
while (i < c)
{
dp[0][i] = data[0][i] + dp[0][i - 1];
i += 1;
}
i = 1;
// iterate the loop through by row
while (i < r)
{
// iterate the loop through by column
while (j < c)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i][j] = data[i][j] + self.minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
);
j += 1;
}
i += 1;
j = 1;
}
// Display calculated result
print("\n Min Cost : ", dp[r - 1][c - 1], terminator: "");
}
}
func main()
{
let data: [[Int]] = [
[1, 3, 1, 2, 3] ,
[2, 1, 1, 2, 8] ,
[1, 2, 8, 7, 3] ,
[1, 2, 3, 2, 5]
];
// Get number of row and column
let r: Int = data.count;
let c: Int = data[0].count;
}
main();``````

#### Output

`` Min Cost :  13``
``````/*
Kotlin Program
Min cost path in matrix
*/
class Cost
{
// Returns the minimum of a given three values
fun minValue(a: Int, b: Int, c: Int): Int
{
if (a > b)
{
if (b > c)
{
return c;
}
else
{
return b;
}
}
else
{
if (a > c)
{
return c;
}
else
{
return a;
}
}
}
// Find minimum cost path in given data matrix
fun minCost(data: Array < Array < Int >> , r: Int, c: Int): Unit
{
// Auxiliary space which are used to find min path
var dp: Array < Array < Int >> = Array(r)
{
Array(c)
{
0
}
};
// Set first point
dp[0][0] = data[0][0];
// Loop controlling variables
var i: Int = 1;
var j: Int = 1;
// Set first column
while (i < r)
{
dp[i][0] = data[i][0] + dp[i - 1][0];
i += 1;
}
i = 1;
// Set first row
while (i < c)
{
dp[0][i] = data[0][i] + dp[0][i - 1];
i += 1;
}
i = 1;
// iterate the loop through by row
while (i < r)
{
// iterate the loop through by column
while (j < c)
{
// minValue(top, top left, and left element)
//  b   a
//    ↖ ↑
//  c ← x
dp[i][j] = data[i][j] + this.minValue(
dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
);
j += 1;
}
i += 1;
j = 1;
}
// Display calculated result
print("\n Min Cost : " + dp[r - 1][c - 1]);
}
}
fun main(args: Array < String > ): Unit
{
var data: Array < Array < Int >> = arrayOf(
arrayOf(1, 3, 1, 2, 3),
arrayOf(2, 1, 1, 2, 8),
arrayOf(1, 2, 8, 7, 3),
arrayOf(1, 2, 3, 2, 5)
);
// Get number of row and column
var r: Int = data.count();
var c: Int = data[0].count();
}``````

#### Output

`` Min Cost : 13``

## Time Complexity

The time complexity of the above algorithm is O(R x C), where R is the number of rows and C is the number of columns in the matrix. This is because we iterate through each cell of the matrix exactly once to fill the dp array.

## Output Explanation

The given code produces the following output:

```Min Cost: 13
```

The output indicates that the minimum cost path from the top-left corner to the bottom-right corner of the given matrix is 13.

## Finally

In this article, we discussed the min cost path problem in a matrix. We presented a pseudocode algorithm that uses dynamic programming to find the minimum cost path. The algorithm has a time complexity of O(R x C). We also explained the output generated by the given code, which indicates the minimum cost of the path.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post