如何用矩阵中的最小和计算从 [0,0] 到 [M, N] 的路径?
How to calculate a path from [0,0] to [M, N] with min sum in a matrix?
我需要计算从 [0,0] 到 [M, N] 的路径,矩阵中的最小和仅向右或向下移动?
我找到了这样的 link 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];
}
能否请您解释一下,如果可能的话请提供您将如何解决?
到达 (m, n) 的路径必须通过以下 2 个单元格之一:(m-1, n) 或 (n-1, m)。所以达到 (m, n) 的最小和可以写成“2 个单元格中的最小值加上 sum[m][n]”。
minSum(m, n) = min (minSum(m-1, n-1), minSum(m-1, n)) + sums[m][n]
我对如何实施广度优先搜索感到有点困惑,但很难理解这里的动态公式,对我来说这似乎更简单:)
这几乎就是经典的动态规划问题。到达任何单元格 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
循环,以 "bottom-up" 顺序访问我们 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,0] 到 [M, N] 的路径,矩阵中的最小和仅向右或向下移动?
我找到了这样的 link 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];
}
能否请您解释一下,如果可能的话请提供您将如何解决?
到达 (m, n) 的路径必须通过以下 2 个单元格之一:(m-1, n) 或 (n-1, m)。所以达到 (m, n) 的最小和可以写成“2 个单元格中的最小值加上 sum[m][n]”。
minSum(m, n) = min (minSum(m-1, n-1), minSum(m-1, n)) + sums[m][n]
我对如何实施广度优先搜索感到有点困惑,但很难理解这里的动态公式,对我来说这似乎更简单:)
这几乎就是经典的动态规划问题。到达任何单元格 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
循环,以 "bottom-up" 顺序访问我们 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));