LeetCode_174_DungeonGame

题目分析：

显然自底向上是无法得知递推初始值的，因为这就是所求结果，只能自顶向下递推，初始值是1。
状态转换方程
  dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]) 
  dp[i][j]代表“从i，j出发”，选择“耗血较少的方向”，走到“下一个”位置，所需最少hp。
  解释一下，如果dp[i][j] < 1，其实是代表在dp[i][j]即使是“死了”，下一个位置也能救回来。
  请牢记，走是顺着走，方程是倒着推的，再看看上面这句话就明白了。
  但是不能死，所以要给一些多余的血量，补充到至少是1。
  方程略微有点复杂，但有前面的基础应该不难分析。
递推初始项
  dp[m-1][i] = max(1, dp[m-1][i+1] - dungeon[m-1][i]);
  dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1]);
  注意:dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]);
举例
输入为
  {{-2, -3,  3},
   {-5, -10, 1},
   { 0,  30,-5}}时
dp初始化为
  {{0, 0, 2},
   {0, 0, 5},
   {1, 1, 6}}

解法一：循环-动态规划

public static int calculateMinimumHP_dp_loop(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int [][]dp = new int[m][n];
    dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);
    for (int i = n - 2; i >= 0 ; --i)
        dp[m-1][i] = Math.max(1, dp[m-1][i+1] - dungeon[m-1][i]);
    for (int i = m - 2; i >= 0 ; --i)
        dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);

    for (int i = m - 2; i >= 0; --i) {
        for (int j = n - 2; j >= 0; --j) {
            dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);
        }
    }
    return dp[0][0];
}

解法二：循环-动态规划-内存优化

public static int calculateMinimumHP_lessMemory(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int []dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[n-1] = 1;

    for (int i = m - 1; i >= 0; --i) {
        /**
         * 同理 手动更新 最右一列
         */
        dp[n-1] = Math.max(1, dp[n-1] - dungeon[i][n-1]);
        for (int j = n - 2; j >= 0; --j) {
            dp[j] = Math.max(1, Math.min(dp[j], dp[j+1]) - dungeon[i][j]);
        }
    }

    return dp[0];
}

解法二分析

Arrays.fill(dp, Integer.MAX_VALUE);这句是为了第一轮初始化的时候设置，排除来自“下方”的选项。

解法三：循环-动态规划-更进一步内存优化

public static int calculateMinimumHP_dp_loop_bestMemory(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    if(m > n) {
        int []dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n-1] = 1;

        for (int i = m - 1; i >= 0; --i) {
            /**
             * 同理 手动更新 最右一列
             */
            dp[n-1] = Math.max(1, dp[n-1] - dungeon[i][n-1]);
            for (int j = n - 2; j >= 0; --j) {
                dp[j] = Math.max(1, Math.min(dp[j], dp[j+1]) - dungeon[i][j]);
            }
        }

        return dp[0];
    }else {
        int []dp = new int[m];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[m-1] = 1;

        for (int i = n - 1; i >= 0; --i) {
            /**
             * 同理 手动更新 最右一列
             */
            dp[m-1] = Math.max(1, dp[m-1] - dungeon[m-1][i]);
            for (int j = m - 2; j >= 0; --j) {
                dp[j] = Math.max(1, Math.min(dp[j], dp[j+1]) - dungeon[j][i]);
            }
        }

        return dp[0];
    }
}

总结

动态规划通常是自底向上的(bottom-up)，但并不绝对，该题就是一个典型的自顶向下(top-down)。

相应例题的 Github