矩阵路径 DP：最小路径和与不同路径

不同路径（LeetCode 62）

机器人从左上角到右下角，只能向右或向下，求路径数：

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    // 第一行和第一列只有一种走法
    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];
    return dp[m-1][n-1];
}

// 滚动数组优化 O(n) 空间
public int uniquePaths(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];
    return dp[n-1];
}

不同路径 II（LeetCode 63）

有障碍物（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; continue; }
            if (j > 0) dp[j] += dp[j-1];
        }
    }
    return dp[n-1];
}

最小路径和（LeetCode 64）

路径上数字和最小，从左上角到右下角：

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // 原地修改（或新建dp数组）
    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];
            else if (j == 0) grid[i][j] += grid[i-1][j];
            else grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    return grid[m-1][n-1];
}

地下城游戏（LeetCode 174）

从左上到右下，每格都有血量变动，求初始最低血量（全程血量 >= 1）：

逆向 DP：从右下角出发，每格需要的最低初始血量：

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int[][] dp = new int[m+1][n+1];  // 边界哨兵
    // 出口右侧、下方最低需要 1 HP
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
    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--) {
            int need = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
            dp[i][j] = Math.max(need, 1); // 至少需要 1 HP
        }
    }
    return dp[0][0];
}

总结