174. Dungeon Game

一开始的思路是，现算出每条路径存入List>，然后算出最小值，最后肯定TLE了。

// compute minHP needed from the start of each path
public static int computeHP(int[] arr) {
    int minHP = 1;

    for (int i = arr.length - 1; i >= 0; i--) {
        minHP = minHP - arr[i];
        minHP = minHP <= 0 ? 1 : minHP;
    }
    return minHP;
}

然后呵呵，照着DP答案强行改写的。。

1.Memorization

public int calculateMinimumHP(int[][] dungeon) {
    // boundary check
    if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;

    int m = dungeon.length;
    int n = dungeon[0].length;
    // init cache
    int[][] cache = new int[m + 1][n + 1];
    return dfs(0, 0, dungeon, cache);
}

public static int dfs(int m, int n, int[][] dungeon, int[][] cache) {
    if (m == dungeon.length - 1 && n > dungeon[0].length - 1) return 1;
    if (m > dungeon.length - 1 && n == dungeon[0].length - 1) return 1;
    if (m > dungeon.length - 1 || n > dungeon[0].length - 1) return Integer.MAX_VALUE;
    if (cache[m][n] == 0) {
        int res = Math.min(dfs(m + 1, n, dungeon, cache), dfs(m, n + 1, dungeon, cache)) - dungeon[m][n];
        cache[m][n] = (res <= 0) ? 1 : res;
    }
    return cache[m][n];
}

1. DP

public int calculateMinimumHP(int[][] dungeon) {
    // boundary check
    if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;

    int m = dungeon.length;
    int n = dungeon[0].length;

    // init cache
    int[][] cache = new int[m + 1][n + 1];

    // fill the last row
    Arrays.fill(cache[m], Integer.MAX_VALUE);

    // fill the last col
    for (int i = 0; i <= m; i++) {
        cache[i][n] = Integer.MAX_VALUE;
    }

    // init min HP
    cache[m][n - 1] = 1;
    cache[m - 1][n] = 1;

    // fill min HP value in cache
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int minHP = Math.min(cache[i + 1][j], cache[i][j + 1]) - dungeon[i][j];
            cache[i][j] = (minHP <= 0) ? 1 : minHP;
        }
    }
    return cache[0][0];
}