LeetCode——地下城游戏

NO.174 地下城游戏困难

思路一：动态规划 dp[i][j]的含义：从第 dungeon[i][j] 走到终点 P 需要的最小生命值。

初始化：dp数组大小[n+1][m+1]，n和m是 dungeon 的行列数，增加最下面一行和最后面一列是为了方便处理，省去边界值判断，增加的行列填充为 Max_Value ；

从右下角终点向左上角终点计算，因为计算 dp[i][j] 需要 dp[i+1][j] 和 dp[i][j-1] ；

dp[n-1][m-1] = dungeon[n-1][m-1]>0 ? 1 : -dungeon[n-1][m-1] + 1，即终点如果是加血，那么只要活着(1滴血)到终点就好了，如果终点需要打怪扣血那么要保持打完怪还活着( -dungeon[n-1][m-1] + 1)。

状态转移方程：dp[i][j] = Min(dp[i+1][j],dp[i][j+1])-dungeon[i][j] ，即选择需要最小生命值的下一个路径，再考虑上当前位置 dungeon[i][j] 的情况；如果 dp[i][j] 求出来是负数，表示当前位置只要活着就行，所以标记为最小的血量 dp[i][j] = 1。

public int calculateMinimumHP(int[][] dungeon) {
    int n = dungeon.length, m = dungeon[0].length;
    int[][] dp = new int[n + 1][m + 1];
    //初始化
    dp[n - 1][m - 1] = dungeon[n - 1][m - 1] > 0 ? 1 : -dungeon[n - 1][m - 1] + 1;
    for (int i = 0; i < n + 1; i++) {
        dp[i][m] = Integer.MAX_VALUE;
    }
    for (int i = 0; i < m + 1; i++) {
        dp[n][i] = Integer.MAX_VALUE;
    }
    //状态转移
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            //终点已经初始化了,不需要重复计算
            if (i == n - 1 && j == m - 1) continue;
            dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            //如果当前位置计算出最小血量为负数或0,说明只需要小血量 活着即可
            if (dp[i][j] <= 0) dp[i][j] = 1;
        }
    }
    return dp[0][0];
}

时间复杂度：O(n*m)

空间复杂度：O(n*m)

空间优化

dp 数组可以直接使用一个一维数组，计算第 i 行的时候，只需要关心 i+1 行

public int calculateMinimumHP(int[][] dungeon) {
    int n = dungeon.length;
    int m = dungeon[0].length;
    int[] dp = new int[m + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[m - 1] = dungeon[n - 1][m - 1] > 0 ? 1 : -dungeon[n - 1][m - 1] + 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i == n - 1 && j == m - 1) continue;
            dp[j] = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
            if (dp[j] <= 0) dp[j] = 1;
        }
    }
    return dp[0];
}

时间复杂度：O(n*m) 空间复杂度：O(m)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.174 地下城游戏 困难

NO.174 地下城游戏困难