Matrix Path DP: Different Paths and Minimum Path Sum

Unique Paths (LeetCode 62)

Count distinct paths from the top-left to the bottom-right of an $m \times n$ grid, moving only right or down.

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // Fill the first row and column: only one way to reach any cell therein
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // Paths from above + paths from left
        }
    }
    return dp[m - 1][n - 1];
}

// Optimization: O(n) space using a rolling array
public int uniquePathsOptimized(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1]; // current cell = cell above + cell to the left
        }
    }
    return dp[n - 1];
}

Unique Paths II (LeetCode 63)

Same as above, but some cells are blocked by obstacles (designated by 1).

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0; // Obstacle blocks all paths through this cell
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

Minimum Path Sum (LeetCode 64)

Find the path with the smallest sum of numbers.

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            else if (i == 0) grid[i][j] += grid[i][j - 1]; // Bound to row 0
            else if (j == 0) grid[i][j] += grid[i - 1][j]; // Bound to col 0
            else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    return grid[m - 1][n - 1];
}

Dungeon Game (LeetCode 174)

Determine the minimum initial health needed for a knight to cross the dungeon. Health must never drop below 1.

Strategy: Reverse DP. Calculate from the bottom-right (destination) back to the top-left (start).

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int[][] dp = new int[m + 1][n + 1];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
    
    // Boundary conditions: to survive at the exit, knight needs 1 HP
    dp[m][n - 1] = dp[m - 1][n] = 1;
    
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            // HP needed to enter current room given the minimum needed for next move
            int need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = Math.max(need, 1); // Must have at least 1 HP at any moment
        }
    }
    return dp[0][0];
}

Summary Selection Guide