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)
{
Cost task = new Cost();
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;
task.minCost(data,r,c);
}
}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()
{
Cost task = Cost();
int data[R][C] = {
{
1 , 3 , 1 , 2 , 3
} , {
2 , 1 , 1 , 2 , 8
} , {
1 , 2 , 8 , 7 , 3
} , {
1 , 2 , 3 , 2 , 5
}
};
task.minCost(data);
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)
{
Cost task = new Cost();
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);
task.minCost(data, r, c);
}
}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()
{
$task = new Cost();
$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]);
$task->minCost($data, $r, $c);
}
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 task = new Cost();
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;
task.minCost(data, r, c);
}
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() :
task = Cost()
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])
task.minCost(data, r, c)
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()
task = Cost.new()
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
task.minCost(data, r, c)
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;
task.minCost(data, r, c);
}
}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 task: Cost = Cost();
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;
task.minCost(data, r, c);
}
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 task: Cost = Cost();
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();
task.minCost(data, r, c);
}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.
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.
New Comment