Dynamic Programming – Minimum Cost Path Problem

Objective: Given a 2D-matrix where each cell has a cost to travel. You have to write an algorithm to find a path from left-top corner to bottom-right corner with minimum travel cost. You can move only right or down.

In the solution we will see that how dynamic programming is much better approach than recursion. Don’t get me wrong, even I like recursion a lot 🙂

Example:

MInimum-Cost-Path-Problem
MInimum-Cost-Path-Problem

Approach:

This problem is similar to Find all paths from top-left corner to bottom-right corner.

We can solve it using Recursion ( return Min(path going right, path going down)) but that won’t be a good solution because we will be solving many sub-problems multiple times. Since at every cell we have 2 options the time complexity will O(2n).

Dynamic Programming:

Create a solution 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 Complexity: O(n2).

Code:

public class MinCostPath {
public static int find(int[][] A) {
int[][] solution = new int[A.length][A.length];
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 column
for (int i = 1; i < A.length; i++) {
solution[i][0] = A[i][0] + solution[i 1][0];
}
// path will be either from top or left, choose which ever is minimum
for (int i = 1; i < A.length; i++) {
for (int j = 1; j < A.length; j++) {
solution[i][j] = A[i][j]
+ Math.min(solution[i 1][j], solution[i][j 1]);
}
}
return solution[A.length 1][A.length 1];
}
public static void main(String[] args) {
int[][] A = { { 1, 7, 9, 2 }, { 8, 6, 3, 2 }, { 1, 6, 7, 8 },
{ 2, 9, 8, 2 } };
System.out.println("Minimum Cost Path " + find(A));
}
}

view raw
MinCostPath.java
hosted with ❤ by GitHub

Output:
Minimum Cost Path 29