给定一个m×n的网格，每个格子上包含一个非负整数。在网格上移动时，每次只能向下或者向右移动一步。请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 样列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 的总和最小。 1-2、请用分支限界法解决此问题，问题分析与算法原理，用java代码实现，并给出相应的解空间的代码实现

问题分析：
本题是一道典型的动态规划问题，可以使用分支限界法来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示从起点到(i,j)位置的最小路径和。因为每次只能向下或向右移动一步，所以我们可以得出状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中grid[i][j]表示网格中该位置的数字。

算法原理：
在分支限界法中，我们需要维护一个优先队列，队列中存储的是状态节点。每次从队列中取出具有最小路径和的节点进行扩展，扩展出的子节点加入队列，并更新当前最小路径和。当遇到终点时，更新全局最小路径和。

Java代码实现：

import java.util.*;

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.sum - b.sum);
        pq.offer(new Node(0, 0, grid[0][0]));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int i = node.i, j = node.j, sum = node.sum;
            if (i == m - 1 && j == n - 1) return sum; // reach the end
            if (i + 1 < m) pq.offer(new Node(i + 1, j, sum + grid[i + 1][j])); // move down
            if (j + 1 < n) pq.offer(new Node(i, j + 1, sum + grid[i][j + 1])); // move right
        }
        return 0;
    }
}

class Node {
    int i, j, sum;
    public Node(int i, int j, int sum) {
        this.i = i;
        this.j = j;
        this.sum = sum;
    }
}

解空间的代码实现：

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.sum - b.sum);
    pq.offer(new Node(0, 0, grid[0][0]));
    while (!pq.isEmpty()) {
        Node node = pq.poll();
        int i = node.i, j = node.j, sum = node.sum;
        if (i == m - 1 && j == n - 1) return sum; // reach the end
        if (i + 1 < m) pq.offer(new Node(i + 1, j, sum + grid[i + 1][j])); // move down
        if (j + 1 < n) pq.offer(new Node(i, j + 1, sum + grid[i][j + 1])); // move right
        System.out.println("Expand node (" + i + ", " + j + "), sum = " + sum);
        System.out.print("Queue: ");
        for (Node q : pq) {
            System.out.print("(" + q.i + ", " + q.j + ") -> " + q.sum + ", ");
        }
        System.out.println();
    }
    return 0;
}