64.最小路径和(递归)

dp递归, m[x][y] = min(dfs(x-1, y), dfs(x, y-1)) + grid[x][y]; 注意: 对于dfs(0, 0)需要特殊处理, 返回零, 不然会因为dfs(0, -1)和dfs(-1, 0)都为Integer.MAX_VALUE导致错误 @param grid @return

class Solution {
    int[][] m;

    /**
     * dp递归,
     *  m[x][y] = min(dfs(x-1, y), dfs(x, y-1)) + grid[x][y];
     * 注意: 对于dfs(0, 0)需要特殊处理, 返回零,
     * 不然会因为dfs(0, -1)和dfs(-1, 0)都为Integer.MAX_VALUE导致错误
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        m = new int[grid.length][grid[0].length];
        for (var row : m) {
            Arrays.fill(row, -1);
        }
        return dfs(grid, grid.length-1, grid[0].length-1);
    }

    /**
     * dfs(x, y): 从(x, y)的方向出发, 最后到达(0, 0), 路径的数字总和的最小值
     */
    private int dfs(int[][] grid, int x, int y) {
        if (x < 0 || y < 0) {
            return Integer.MAX_VALUE;
        }
        if (x == 0 && y == 0) return grid[0][0];
        if (m[x][y] != -1) return m[x][y];

        m[x][y] = Math.min(dfs(grid, x-1, y), dfs(grid, x, y-1)) + grid[x][y];

        return m[x][y];
    }
}