Minimum cost path

Problem : Given a matrix and start point and end point what is the minimum cost to reach from start point to end point. Given that you can only go right or down.

Basic idea is that for each node you can only either come from up or down. Start from 0,0 and for each node check the minimum path from both directions. For row = 0, there is only right direction to go so keep adding the cost . for column = 0 there is only down direction to go. For rest of the T[i][j] check T[i][j] = T[i][j] +Min( T[i-1][j]], T[i][j-1] ). This will give the total sum for each node in the matrix. To back track and find the path. check where the sum came from and add that value in the array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

public int[] minimumCostPath(int[][] input){ // total number of nodes traversed would be m+n-1 if(input.length < 1 || input[0].length < 1){ return new int [] {0}; } int[] result = new int[input.length + input[0].length - 1]; int total = input[0][0]; for(int i = 0; i < input.length; i++){ for(int j = 0; j< input[i].length; j++){ if(i == 0 && j != 0){ input[i][j] = input[i][j] + input[i][j-1]; total = input[i][j]; }else if(j != 0 && i != 0){ input[i][j] = Math.min(input[i][j] + input[i-1][j], input[i][j] + input[i][j-1]); total = input[i][j]; }else if(j == 0 && i != 0){ input[i][j] = input[i][j] + input[i-1][j]; total = input[i][j]; } } } //get path; int path = result.length -1; int i = input.length-1; int j = input[0].length -1; while(total != 0){ if(i > 0 && j > 0){ if(input[i-1][j] < input[i][j-1]){ result[path] = total-input[i-1][j]; total = input[i-1][j]; i = i-1; path--; }else{ result[path] = total - input[i][j-1]; total = input[i][j-1]; j = j-1; path--; } }else if(j == 0 && i != 0){ result[path] = total - input[i-1][j]; total = input[i-1][j]; i = i-1; path--; }else if(i == 0 && j != 0){ result[path] =total - input[i][j-1]; total = input[i][j-1]; j = j-1; path--; } else if(i == 0 && j == 0){ result[path] = input[i][j]; total = total - input[i][j]; path--; } } return result; }