Problem

You are given a matrix of size m by n. You have to travel from the corner (0,0) to (m-1,n-1) of the matrix. Each entry of the matrix represents the cost to step on it. You are required to find the minimum possible cost to complete the journey.

Example


Code


/**
 *
 * @author UmerSoftwares
 */
import java.util.Scanner;
public class MinimumCost {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.print("Enter the width  of the array: ");
        int w=in.nextInt();
        System.out.print("Enter the height of the array: ");
        int h=in.nextInt();
       
        int[][] arr=new int[h][w];
        for (int i=0;i<h;i++){
            System.out.println("Enter line number "+(i+1)+" separated by spaces");
            for (int j=0;j<w;j++){
                arr[i][j]=in.nextInt();
            }
        }
        int result=lessCost(arr,0,0);
        System.out.println("Result: "+result);
    }
    public static int lessCost(int[][] arr,int x,int y){
        int width=arr.length;
        int height=arr[0].length;
        int less=Integer.MAX_VALUE;
        if (x==width-1 && y==height-1){
            return arr[width-1][height-1];
        }else{
            if ((!(x==width-1))&& (!(y==height-1))){
                int try1=lessCost(arr,x+1,y);
                int try2=lessCost(arr,x,y+1);
                if (try1<less){
                    less=try1;
                }
                if (try2<less){
                    less=try2;
                }
            }
            if (x==width-1){
                int try1=lessCost(arr,x,y+1);
                if (try1<less){
                    less=try1;
                }
            }
            if (y==height-1){
                int try1=lessCost(arr,x+1,y);
                if (try1<less){
                    less=try1;
                }
            }
           
        }
        return less+arr[x][y];
    }
   
}

Explanation

Let's consider we have the following matrix

We have to move from the top left corner of this matrix to the bottom right corner.

We will not move up and left

In our journey, we will never move up and left because it will simply add to our cost and we will not be able to find the minimum cost. Let's consider the following path which includes upward and left movement:

We can surely reduce the cost by elimination the upward and left movements. This is common sense

So it is confirmed that we will only move right and down.


We will design a recursive function

Our function will call itself over a smaller part of it. For example, if we start from the top left end and move one step right. Now the smaller part will be: (Highlighted in picture below)

Similarly, if we move one step down instead of right, the smaller part will be:

Our function will call itself over its two smaller parts. One that is obtained by moving towards right and one that is obtained by moving down. It will compare the results returned by both to determine which leads to the path with minimum cost (part that will return less cost will be leading to the minimum cost path)

Our recursive function will keep on calling itself over its smaller parts. The base case will be the one when it reaches the end like this:

In this case, the cost will be the number that is present in the last cell. (In this case 6)

In our particular example, the path followed by the program as the minimum cost path will be:


The cost of this path will be 3+0+4+0+1+1+2+4+9+6=30. You can verify this by giving the above matrix as an input to the program.

If you have any questions, you can ask in the comments.