递归式动态规划最小路径和代码疑问：两种写法差异解析

我在求解动态规划最小路径和问题时，自己写的递归解法逻辑看似正确却无法运行，代码如下：

class Solution {
    public int minPathSum(int[][] arr) {
        return f(arr.length-1, arr[0].length-1, arr);
    }

    public int f(int i, int j, int[][] arr) {
        if (i < 0 || j < 0) return Integer.MAX_VALUE;
        if (i == 0 && j == 0) return arr[0][0];
        int up = arr[i][j] + f(i-1, j, arr);
        int left = arr[i][j] + f(i, j-1, arr);
        return Math.min(up, left);
    }
}

而网上找到的递归解法可以正常运行：

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length-1;
        int n = grid[0].length-1;
        return find(grid, m, n);
    }

    public int find(int grid[][], int m, int n) {
        if (m < 0 || n < 0) return Integer.MAX_VALUE;
        if (m == 0 && n == 0) return grid[0][0];
        return grid[m][n] + Math.min(find(grid, m-1, n), find(grid, m, n-1));
    }
}

两者的核心差异在于加法操作的时机，下面具体分析：

错误根源：整数溢出 #

你的代码会对所有递归分支的结果执行加法，包括边界情况返回的Integer.MAX_VALUE。Java中int是有符号32位整数，当正数与Integer.MAX_VALUE相加时，会触发整数溢出，结果变成负数（比如2 + Integer.MAX_VALUE会等于Integer.MIN_VALUE +1，是一个负数）。

举个具体场景：当计算第一行（i=0）的某个位置（j>0）时，up = arr[0][j] + f(-1,j,arr)，这里f(-1,j,arr)返回Integer.MAX_VALUE，相加后得到负数。后续Math.min(负数, left)会错误地选择这个负数，导致最终结果完全偏离正确值。

可行解法的正确逻辑 #

可行代码先通过Math.min筛选出有效的最小路径和，再与当前格子的值相加：

• 当某个递归分支返回Integer.MAX_VALUE（比如越界情况），Math.min会直接忽略这个无效值，选择另一个有效的路径和（比如左方或上方的有效路径）；
• 只对筛选后的有效路径和执行加法，完全避免了溢出问题。

比如同样计算第一行的位置（0,j）：
grid[0][j] + Math.min(find(-1,j), find(0,j-1)) → Math.min(Integer.MAX_VALUE, 有效路径和)会直接取有效路径和，再加当前值得到正确结果。

总结差异 #

• 你的写法：先对所有递归结果（包括无效的MAX_VALUE）执行加法，触发溢出；
• 可行写法：先筛选有效路径和，再执行加法，避免溢出。

内容的提问来源于stack exchange，提问作者Suryanarayanan