浅析：最小路径和

64. 最小路径和

今天我们来详细分析一波 最小路径和，带你从头开始一步一步得到最优化的解决方案！

暴力 DFS

首先第一眼看到这个题目，自然而然想到的就是 DFS，遍历出所有的路径，然后得到和最小的路径

关于 DFS 详细的内容可见 回溯 (DFS) 算法框架

x
// 记录最小路径和
private int res = Integer.MAX_VALUE;
public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // 从 (0, 0) 开始遍历
    dfs(grid, 0, 0, 0, new boolean[m][n]);
    return res;
}
private void dfs(int[][] grid, int i, int j, int pathSum, boolean[][] used) {
    int m = grid.length;
    int n = grid[0].length;
    // 先序阶段：首次进入节点 (i, j)
    // 越界
    if (i < 0 || i >= m || j< 0 || j >= n) return ;
    // 判断是否已经被使用
    if (used[i][j]) return;
    // 标记已被使用
    used[i][j] = true;
    // 添加到路径中
    pathSum += grid[i][j];
    // 到达终点
    if (i == m - 1 && j == n - 1) res = Math.min(res, pathSum);
    
    // 每次都往「下」「右」进行搜索
    dfs(grid, i + 1, j, pathSum, used);
    dfs(grid, i, j + 1, pathSum, used);
    
    // 后续阶段：即将离开节点 (i, j)
    pathSum -= grid[i][j];
    used[i][j] = false;
}

很显然，这个是超时的！！！

备忘录 + 递归

上面是没有任何优化的暴力 DFS，可以很明显的看到其实是存在「重叠子问题」的

这里采用自顶向下的解法，所以会有一个递归的dp函数，一般来说函数的参数就是状态转移中会变化的量，即：「状态」；函数的返回值就是grid[0..i][0..j]的最小路径和

x
private int res = Integer.MAX_VALUE;
public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    return dp(grid, m - 1, n - 1, new int[m][n]);
}
private int dp(int[][] grid, int i, int j, int[][] emeo) {
    int m = grid.length;
    int n = grid[0].length;
    // base case
    if (i < 0 || i >= m || j< 0 || j >= n) return Integer.MAX_VALUE;
    if (emeo[i][j] != 0) return emeo[i][j];

    int minPathSum = Math.min(dp(grid, i - 1, j, emeo), dp(grid, i, j - 1, emeo));

    emeo[i][j] =  minPathSum == Integer.MAX_VALUE ? grid[i][j] : minPathSum + grid[i][j];

    return emeo[i][j];
}

DP + 递推

明确 base case：显然是当i = 0 and j = 0，最小路径和直接是grid[0][0]

明确「状态」：原问题和子问题中会发生变化的变量。grid[0..i][0..j]会不断地向 base case 靠近，所以唯一的「状态」就是矩阵grid[0..i][0..j]

明确「选择」：导致「状态」产生变化的行为。矩阵grid[0..i][0..j]为什么变化呢？因为在选择不同的方向，每选择一种方向，矩阵就会收缩。所以说「上方 or 左方」就是「选择」(每次都可在选择任意一种方向)

明确 dp 数组/函数的定义：这里采用自底向上的解法，所以会有一个递推的dp数组，一般来说数组的下标就是状态转移中会变化的量，即：「状态」；数组的值就是grid[0..i][0..j]的最小路径和

关于dp[]的初始状态，直接看下图：

x
public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m + 1][n + 1];
    // 初始化 dp[]
    for (int i = 0; i < dp.length; i++) dp[i][0] = Integer.MAX_VALUE;
    for (int j = 0; j < dp[0].length; j++) dp[0][j] = Integer.MAX_VALUE;
    dp[0][1] = 0;
    dp[1][0] = 0;
    
    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }
    return dp[m][n];
}