下降路径最小和 -「回溯」&「动规」

931. 下降路径最小和

本篇文章想通过题目 下降路径最小和 详细分析一下关于「base case」和「备忘录 emeo」的初始值确定相关问题！！

但是文章的最开始还是想先分析该题目如何从「暴力回溯」到「回溯 + 备忘录优化」以及到最后的「递推 + dp」的整个过程

遇到一个问题，这里建议一种思考的方向：(PS：关于下面涉及到的一些名词，如果有不理解的，可以先看「回溯 (DFS) 算法框架」和「动态规划解题套路框架」)

• 首先思考是否可以通过「暴力回溯」写出来
• 然后观察是否存在「重叠子问题」，如果存在自然就想到通过「备忘录 emeo」优化
• 至于能不能改写成「递推 + dp」的方法，这个需要看该题目是否存在「最优子结构」

下面用大白话解释一下上面说的内容

其实「暴力回溯」就是穷举所有可能性，找到满足题目要求的最优解；在穷举的过程中可以通过「剪枝」去除一些不需要遍历的分支；如果存在「重叠子问题」，我们还可以通过「备忘录 emeo」的方法优化 -> 傻瓜式遍历

在上面的基础上，如果我们可以通过前面已经计算出的状态推出当前状态，那么就可以采用「递推 + dp」的方法。之所以可以通过「(状态1，状态2，...) -> 当前状态」，是因为存在「最优子结构」，每一种「状态」对应一种「子结构」

有些题目，要求得到所有的可行解，但是既不存在「重叠子问题」，也不存在「最优子结构」，那么就只能用「傻瓜式的回溯」穷举所有可能。不过可以通过「剪枝」去除一些不需要遍历的分支，如题目 括号生成，该题目的详细分析可见 回溯算法：括号生成

有些题目，虽然只要求得到一个可行解，但是不存在「最优子结构」，所以也只能用「傻瓜式的回溯」穷举所有可能。如果存在「重叠子问题」就可以通过「备忘录」优化，如题目 划分为k个相等的子集，该题目的详细分析可见 经典回溯算法：集合划分问题

有些题目，既存在「重叠子问题」，也存在「最优子结构」，所以既可以使用「回溯」的方法，也可以使用「递推 + dp」的方法，如我们今天要分析的题目

三种方法

下面使用上述介绍的思路，即三种不同的方法来解决该问题

暴力回溯

其实不难，注释已经很详细，配合注释看，相信大家可以看懂！！

private int n;
public int minFallingPathSum(int[][] matrix) {
    this.n = matrix.length;
    int ans = Integer.MAX_VALUE;
    // 从第一行的每一个位置开始搜索
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, backtrack(matrix, 0, i));
    }
    return ans;
}
private int backtrack(int[][] matrix, int row, int col) {
    // 结束条件：到达最后一行 (和 N 皇后很像)
    if (row == n) return 0;
    // 向正下方遍历
    int path = backtrack(matrix, row + 1, col);
    if (col - 1 >= 0) {
        // 向左下方遍历
        path = Math.min(path, backtrack(matrix, row + 1, col - 1));
    }
    if (col + 1 < n) {
        // 向右下方遍历
        path = Math.min(path, backtrack(matrix, row + 1, col + 1));
    }
    // path 为子问题的最小值
    // 返回 path + 加上当前值
    // 和「树的后序遍历」➕「分解子问题的思路」很像
    return path + matrix[row][col];
}

回溯 + 备忘录优化

很容易看出这个问题存在「重叠子问题」，可以通过一个二维数组表示一个子问题，下面给出优化后的代码

xxxxxxxxxx
private int n;
// 存储子问题的结果
private int[][] emeo;
public int minFallingPathSum(int[][] matrix) {
    this.n = matrix.length;
    emeo = new int[n][n];
    // 初始化备忘录 emeo
    // 至于为什么初始化为 -66666，下面会详细分析
    for (int i = 0; i < n; i++) Arrays.fill(emeo[i], -66666);
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, backtrack(matrix, 0, i));
    }
    return ans;
}
private int backtrack(int[][] matrix, int row, int col) {
    if (row == n) return 0;
    // 说明该子问题已经有结果，直接返回
    if (emeo[row][col] != -66666) return emeo[row][col];
    int path = backtrack(matrix, row + 1, col);
    if (col - 1 >= 0) {
        path = Math.min(path, backtrack(matrix, row + 1, col - 1));
    }
    if (col + 1 < n) {
        path = Math.min(path, backtrack(matrix, row + 1, col + 1));
    }
    // 存储该子问题结果
    emeo[row][col] = path + matrix[row][col];
    return emeo[row][col];
}

递推 + dp

下面介绍递推的方法，这次先分析一下 base case，直接看图：

最外面一圈就是 base case 的值，至于为什么这样设置，可以看箭头，箭头的方向就是状态转移的方向，即：

dp[i][j] = min(
    dp[i - 1][j],       // 正上方
    dp[i - 1][j - 1],   // 左上方
    dp[i - 1][j + 1]    // 右上方
);

下面可以很容易写出完整代码

public int minFallingPathSum(int[][] matrix) {

    int[][] dp = new int[matrix.length + 1][matrix.length + 2];
    int n = dp.length;
    // base case
    for (int i = 1; i < n; i++) {
        dp[i][0] = Integer.MAX_VALUE;
        dp[i][n] = Integer.MAX_VALUE;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = matrix[i - 1][j - 1] + Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1]));
        }
    }
    // 所以可行解都在 dp[n - 1][1...n-1] 中
    int ans = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) ans = Math.min(ans, dp[n - 1][i]);
    return ans;
}

分析 BASE CASE 和备忘录的初始值

首先来看这一行代码：for (int i = 0; i < n; i++) Arrays.fill(emeo[i], -66666);

为什么要初始化-66666？

根据题目给出的范围

• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

可以算出路径的范围[-10000, 10000]，这已经是极限范围了，所以绝对取不到-66666这个值

关于 base case 的初始化，见上面的图！！