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)
    {
        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
Trace the minimum path in matrix

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.

New Comment