Monday, January 19, 2015

Dungeon game

Leetcode link.

I tried three methods:
First, this really looks like max path sum problem. But soon I realized the short coming of using max path sum, that is, max path sum cannot guarantee that hero's health is always positive (In the following analysis, I assume the health can reach 0. To get the correct output I only need to increment my result by 1).
The sub-problem of max path sum problem is "max value one can at location matrix[i][j]  starting from matrix[0][0]", a similar sub-problem is constructed for this problem, that is:

minimum starting health required to get to location matrix[i][j].

This sub problem requires one to record cumulative health along the way, for example, if the path is -2 -3 3 1 -5, then the minimum starting health sequence is 2 5 5 5 6. To generate this sequence, one need to record cumulative health.
But this method fails too when I encounter this test case:

1     -3     3

0     -2     0

-3    -3     -3

The minimum starting health required to get to matrix[1][2] is 2, and minimum starting health required to get to matrix[2][1] is 5. Thus by my sub problem analysis, one would pick path
1, down, 0, right -2, right, 0, down, -3.
But this path needs a minimum starting health of 4, while path
1, right -3, right, 3, down, 0, down, -3
only needs 2 starting health.
Now we have a problem, sub-problem matrix[2][2] does not come from sub-problem matrix[1][2] or sub-problem matrix[2][1]. This DP structure is not applicable anymore.

I am really frustrated until this problem is reviewed again: problem statement:

minimum initial health to get to the right-down-most cell.

My second method constructs sub-problem from the "fixed-starting-point" POV, if one use "fixed-ending-point" POV, one can construct sub-problem:

minimum health starting from current location to get to the right-down-most cell.

If method 2 (wrong method) is used, one needs two memoization matrices. Further thinking reveals one memoization matrix is enough is method 3 is used. And code length is minimized.

int calculateMinimumHP(vector<vector<int> > &dungeon) {
    if (!dungeon.size() || !dungeon[0].size()) return 1;
    int rowcount(dungeon.size()), colcount(dungeon[0].size());

    vector<int> mi(colcount, 0);
    mi[colcount - 1] = max(0, -dungeon[rowcount - 1][colcount - 1]);
    for (int row = rowcount - 1; row >= 0; --row) {
        for (int col = colcount - 1; col >= 0; --col) {
            if (row == rowcount - 1 && col == colcount - 1) continue;
            int candright(INT_MAX), canddown(INT_MAX);
            if (col != colcount - 1) candright = max(0, -dungeon[row][col] + mi[col + 1]);
            if (row != rowcount - 1) canddown = max(0, -dungeon[row][col] + mi[col]);
            mi[col] = min(candright, canddown);
        }
    }
    return mi[0] + 1;
}

Now it's time to think why method 3 works but not method 2? Leetcode says local minimum cannot guarantee global minimum, but that is just a result, not a formal proof.