样列1： 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。 样列2： 输入：grid = [[1,2,3],[4,5,6]] 输出：12 解释：因为路径 1→2→3→6 的总和最小。分支限界法，java代码实现

以下是使用分支限界法求解最小路径和的Java代码实现：

import java.util.*;

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        boolean[][] visited = new boolean[m][n];
        
        pq.offer(new State(0, 0, grid[0][0]));
        
        while (!pq.isEmpty()) {
            State curr = pq.poll();
            
            if (curr.row == m - 1 && curr.col == n - 1) {
                return curr.cost;
            }
            
            if (visited[curr.row][curr.col]) {
                continue;
            }
            
            visited[curr.row][curr.col] = true;
            
            if (curr.row < m - 1) {
                pq.offer(new State(curr.row + 1, curr.col, curr.cost + grid[curr.row + 1][curr.col]));
            }
            
            if (curr.col < n - 1) {
                pq.offer(new State(curr.row, curr.col + 1, curr.cost + grid[curr.row][curr.col + 1]));
            }
        }
        
        return -1;
    }
    
    private static class State {
        int row;
        int col;
        int cost;
        
        public State(int row, int col, int cost) {
            this.row = row;
            this.col = col;
            this.cost = cost;
        }
    }
}

该算法的基本思路是维护一个优先队列，将所有可以到达的状态按照路径长度从小到大排列，每次取出队首的状态，如果该状态是终点，则返回路径长度，否则拓展该状态的所有邻居状态，并加入优先队列。由于我们可以保证每次取出的状态一定是路径长度最小的，因此可以使用该算法求解最小路径和问题。