How to calculate a path from [0,0] to [M, N] with min sum in a matrix?

Question

I need to calculate a path from [0,0] to [M, N] with min-sum in a matrix moving only right or down?

I found such link https://www.programcreek.com/2014/05/leetcode-minimum-path-sum-java/ but Dynamic Programming option is not clear at all.

I was trying to implement it on my own with BFS algorithm but it is a slow solution

public int minPathSum(final int[][] grid) {
        if (grid.length == 1 && grid[0].length == 1) {
            return grid[0][0];
        }
        final int[][] moves = {new int[]{1, 0}, new int[]{0, 1}};
        final Queue<int[]> positions = new ArrayDeque<>();
        final Queue<Integer> sums = new ArrayDeque<>();
        positions.add(new int[]{0, 0});
        sums.add(grid[0][0]);
        int minSum = Integer.MAX_VALUE;
        while (!positions.isEmpty()) {
            final int[] point = positions.poll();
            final int sum = sums.poll();
            for (final int[] move : moves) {
                final int x = point[0] + move[0];
                final int y = point[1] + move[1];
                if (x == grid.length - 1 && y == grid[0].length - 1) {
                    minSum = Math.min(minSum, sum);
                } else if (x > -1 && y > -1 && x < grid.length && y < grid[0].length) {
                    positions.add(new int[]{x, y});
                    sums.add(sum + grid[x][y]);
                }
            }
        }
        return minSum + grid[grid.length - 1][grid[0].length - 1];
    }

Could you please explain and if possible provide how will you solve it?

Answer 1

I'm a bit confused by how you could implement a breadth first search but have trouble understanding the dynamic formulation here, which to me seems simpler :)

This is pretty much the classic dynamic programming problem. Arriving at any cell, solution[y][x], except the first, has at most two predecessors: option 1 and option 2. Assume that we knew the optimal solution for reaching each of those, which edge would we choose? Clearly the better of the two options!

Slightly more formally, if M holds the given values:

solution[0][0] = M[0][0]

// only one choice along
// the top horizontal and
// left vertical

solution[0][x] =
  M[0][x] + solution[0][x - 1]

solution[y][0] =
  M[y][0] + solution[y - 1][0]

// two choices otherwise:
// the best of option 1 or 2

solution[y][x] =
  M[y][x] + min(
    solution[y][x - 1],
    solution[y - 1][x]
  )

We can see that we can create an appropriate routine, with for loops for example, to visit the cells of our solution matrix in "bottom-up" order since each cell's value depends on one or two predecessors that we would have already calculated.

JavaScript code:

function show(M){
  let str = '';
  for (let row of M)
    str += JSON.stringify(row) + '\n';
  console.log(str);
}

function f(M){
  console.log('Input:\n');
  show(M);
  
  let solution = new Array();
  for (let i=0; i<M.length; i++)
    solution.push(new Array(M[0].length).fill(Infinity));
    
  solution[0][0] = M[0][0];

  // only one choice along
  // the top horizontal and
  // left vertical
  
  for (let x=1; x<M[0].length; x++)
    solution[0][x] =
      M[0][x] + solution[0][x - 1];

  for (let y=1; y<M.length; y++)
    solution[y][0] =
      M[y][0] + solution[y - 1][0];
      
  console.log('Solution borders:\n');
  show(solution);

  // two choices otherwise:
  // the best of option 1 or 2

  for (let y=1; y<M.length; y++)
    for (let x=1; x<M[0].length; x++)
      solution[y][x] =
        M[y][x] + Math.min(
          solution[y][x - 1],
          solution[y - 1][x]
        );
        
  console.log('Full solution:\n');
  show(solution);
  
  return solution[M.length-1][M[0].length-1];
}

let arr = [];
arr[0] = [0, 7, -7];
arr[1] = [6, 7, -8];
arr[2] = [1, 2, 0];

console.log(f(arr));

Answer 2

The path to reach (m, n) must be through one of the 2 cells: (m-1, n) or (n-1, m). So minimum sum to reach (m, n) can be written as “minimum of the 2 cells plus sum[m][n]”.

minSum(m, n) = min (minSum(m-1, n-1), minSum(m-1, n)) + sums[m][n]