给定一个m×n的网格,每个格子上包含一个非负整数。在网格上移动时,每次只能向下或者向右移动一步。请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。请用分支限界法解决该问题,使用java语言。样列1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
时间: 2024-03-19 19:45:27 浏览: 18
以下是使用Java实现分支限界法求解该问题的代码:
```
import java.util.*;
public class MinPathSum {
static class Node implements Comparable<Node> {
int i, j, sum;
public Node(int i, int j, int sum) {
this.i = i;
this.j = j;
this.sum = sum;
}
public int compareTo(Node o) {
return sum - o.sum;
}
}
public static int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 用数组记录到达每个节点的最小路径和
int[][] minSum = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
minSum[i][j] = Integer.MAX_VALUE;
}
}
minSum[0][0] = grid[0][0];
// 用优先队列实现分支限界搜索
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(0, 0, minSum[0][0]));
while (!pq.isEmpty()) {
Node node = pq.poll();
int i = node.i;
int j = node.j;
int sum = node.sum;
if (i == m - 1 && j == n - 1) { // 到达目标节点,返回最小路径和
return sum;
}
if (i < m - 1) { // 向下走
int newSum = sum + grid[i + 1][j];
if (newSum < minSum[i + 1][j]) { // 只添加新路径和更小的节点
minSum[i + 1][j] = newSum;
pq.offer(new Node(i + 1, j, newSum));
}
}
if (j < n - 1) { // 向右走
int newSum = sum + grid[i][j + 1];
if (newSum < minSum[i][j + 1]) { // 只添加新路径和更小的节点
minSum[i][j + 1] = newSum;
pq.offer(new Node(i, j + 1, newSum));
}
}
}
return -1; // 没有找到合法路径
}
public static void main(String[] args) {
int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
int minSum = minPathSum(grid);
System.out.println(minSum);
}
}
```
代码中使用了一个大小为 $(m+n)\times2$ 的数组 $minSum$,其中 $minSum[i][j]$ 表示到达网格 $(i,j)$ 的最小路径和。在分支限界搜索中,每次取出路径和最小的节点并尝试向下或向右走,如果新路径和比已有的更小,则记录新的最小路径和并将新节点加入优先队列中。如果搜索到达目标节点,则返回最小路径和。如果搜索结束后仍未找到合法路径,则返回 $-1$。
时间复杂度为 $O(mn\log(m+n))$,空间复杂度为 $O(mn)$。