回溯算法求解 A点到B点最小距离

需求：

有二维数组，例如：
{5,2,6,3}
{1,4,8,1}
{3,2,6,3}
{9,3,7,2}
每个数字代表代表一条路，数字是路的长度。
求从左上角走到右下角，最短距离是多少？每次只能向右或向下走，不能往上或往左走。
我们使用回溯算法如何求解？

分析：这个题目的起点和终点是固定的，从左上到右下，那么用回溯算法就是遍历所有解，然后选出最优解，解法用递归来解决。

我们计算过程中只有两种可能，向下或向右，直到走到终点，到重点后用结果和最小值比较，小于当前最小值则更新最小值。

/**
 * 回溯算法求解 A点到B点最小距离
 */
public class HuiSu_MinDist {

    private static int minDist = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[][] arr = {
                {5,2,6,3},
                {1,4,8,1},
                {3,2,6,3},
                {9,3,7,2}
        };

        findMinDist(0,0,arr,0,3);
        System.out.println("最小距离:" + minDist);


    }

    /**
     * 回溯算法 最短路径
     * @param i
     * @param j
     * @param arr
     * @param dist
     * @param n 这里是重点，j最大是多少，n就是多少，也就是n=max(j)
     */
    public static void findMinDist(int i, int j, int[][] arr, int dist, int n) {
        if(i==n && j==n) {
            if(dist<minDist) {
                minDist = dist+arr[n][n];
            }
            return;
        }

        if(i<n) {
            findMinDist(i+1,j,arr,dist + arr[i][j],n);
        }

        if(j<n) {
            findMinDist(i,j+1,arr,dist + arr[i][j],n);
        }

    }


}

/* 输出
最小距离:22
 */