LeetCode 64. Minimum Path Sum

Leetcode : MinimumPathSum

类型：动态规划

题目

给一个 MxN的数组矩阵，矩阵上每一个左表代表该点的路径长度，求从左上角到右下角路径的最短的和。
举栗：

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output : 7 (因为最短路径是1-3-1-1-1)

思路

解法可以有两种，动态规划 和 回溯法。
回溯法在这个问题下时间复杂度太高，是指数级。
动态规划的时间复杂度是 O(MxN) M和N是矩阵的长和宽

解法

动态规划

思路：
令矩阵中[0][0] 到 [x][y] 点的最短路径为 minPath(x,y)
则可以得到递推公式：
minPath(x,y) = Math.min(minPath(x-1,y), minPath(x,y-1)) + grid[x][y]

则从(0,0)到矩阵上任意一点的最短路径都可以求得，最终的minPath(m-1,n-1) 就是我们要求的结果

leetcode submit beats 99.4% - 5ms
下面上代码：

public static int minPathSum_DP(int[][] grid) {
        int width = grid[0].length;
        int height = grid.length;
        int[][] minDp = new int[height][width];
        int minUp, minLeft;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(i==0 && j==0){
                    minDp[i][j] = grid[i][j];
                    continue;
                }else if(i==0){
                    minDp[i][j] = minDp[i][j-1] + grid[i][j];
                    continue;
                }else if(j==0){
                    minDp[i][j] = minDp[i-1][j] + grid[i][j];
                    continue;
                }
                minLeft = minDp[i][j-1];
                minUp = minDp[i-1][j];
                minDp[i][j] = minLeft < minUp ? minLeft + grid[i][j] : minUp + grid[i][j];
            }
        }

        return minDp[height-1][width-1];
    }

回溯法
当然另一个思路是使用回溯法，但是回溯法执行时间太长，时间复杂度是指数级的。不过可以作为练习回溯法的一个TestCase

回溯法的思路是把解题的方式当做对一个树的深度优先遍历
该问题下可以进一步优化，在每一次往深了走的时候都校验一下是否已经超过目前已知最短路径，超过就直接返回，不在计算。

代码如下：

    static int minPath =0;
    static int width=0;
    static int height=0;
    public static int minPathSum_BC(int[][] grid) {
        width = grid[0].length;
        height = grid.length;
        backTracing(0,0,0,grid);
        return minPath;
    }

    // 回溯法要注意，由于在一个边到顶以后还要回溯另一个边
    // 所以数组的临界条件不能越界, 也就是如下 w==width-1 && h==height-1
    // 相应的，递归的临界条件也应该使得下一层不能越界
    static void backTracing(int tmp, int h, int w, int[][] grid){
        tmp += grid[h][w];
        if(minPath !=0 && tmp >= minPath){
            return;
        }

        if(h==height-1 && w==width-1){
            minPath = minPath == 0 ? tmp : (tmp<minPath ? tmp : minPath);
            return;
        }

        if(h < height-1){    // 递归下一层不能越界
            backTracing(tmp, h+1, w, grid);
        }
        if(w < width-1){   // 递归下一层不能越界
            backTracing(tmp, h, w+1, grid);
        }
    }