Как рассчитать путь от [0,0] до [M, N] с минимальной суммой в матрице? - PullRequest
Новая
       33

Как рассчитать путь от [0,0] до [M, N] с минимальной суммой в матрице?

3 голосов
/ 16 марта 2019

Мне нужно рассчитать путь от [0,0] до [M, N] с минимальной суммой в матрице, движущейся только вправо или вниз?

Я нашел такую ​​ссылку https://www.programcreek.com/2014/05/leetcode-minimum-path-sum-java/, но опция динамического программирования не совсем ясна.

Я пытался реализовать его самостоятельно с помощью алгоритма BFS, но это медленное решение 

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];
    }

Не могли бы вы объяснить и, если возможно, представить, как вы это решите?

Ответы [ 2 ]

2 голосов
/ 16 марта 2019

Я немного озадачен тем, как вы могли бы осуществить поиск в ширину, но у меня возникли проблемы с пониманием динамической формулировки, что мне кажется проще:)

Это в значительной степени классическая проблема динамического программирования. При поступлении в любую ячейку solution[y][x], кроме первой, имеет не более двух предшественников: option 1 и option 2. Предположим, что мы знали оптимальное решение для достижения каждого из них, какое преимущество мы бы выбрали? Очевидно, лучший из двух вариантов!

Чуть более формально, если M содержит заданные значения: 

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]
  )

Мы можем видеть, что мы можем создать соответствующую подпрограмму, например, с помощью циклов for, чтобы посещать ячейки нашей матрицы solution в порядке «снизу вверх», поскольку значение каждой ячейки зависит от одного или двух предшественников, которые мы бы уже рассчитали.

Код JavaScript: 

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));
0 голосов
/ 16 марта 2019

Путь для достижения (m, n) должен быть через одну из 2 ячеек: (m-1, n) или (n-1, m).Таким образом, минимальная сумма для достижения (m, n) может быть записана как «минимум из 2 ячеек плюс сумма [m] [n]». 

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