0
$\begingroup$

Example of start top-left, Coin Collecting problem in grid: https://www.youtube.com/watch?v=94FEC_uNwVM

Example of start bottom-right, Dungeon Game problem in grid: https://leetcode.com/problems/dungeon-game/description/

I knew the Coin Collecting problem, so I started trying to solve Dungeon Game the same way, starting from the top-left (although it can also be solved bottom-right). Turns out Dungeon Game is solved from the bottom-right. How do I recognize this earlier?

function initTable(m, n, f) {
  var T = [];
  for (var r = 0; r < m; r++)
    T.push(Array(n).fill(f));
  return T;
}

var grid = [
  [-2,-3,3],
  [-5,-10,1],
  [10,30,-5],
];

function calculateMinimumHPFromTopLeft(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[0][1] = 1;
    hp[1][0] = 1;

    for (var i = 1; i < M+1; i++) {
        for (var j = 1; j < N+1; j++) {
            var need = Math.min(hp[i-1][j], hp[i][j-1])-dungeon[i-1][j-1];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[M][N];
}

function calculateMinimumHPFromBottomRight(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[M][N-1] = 1;
    hp[M-1][N] = 1;

    for (var i = M-1; i >= 0; i--) {
        for (var j = N-1; j >= 0; j--) {
            var need = Math.min(hp[i+1][j], hp[i][j+1])-dungeon[i][j];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[0][0];
}

console.log(calculateMinimumHPFromTopLeft(grid))   // 6 (wrong)
console.log(calculateMinimumHPFromBottomRight(grid))  // 7 (correct)
$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, fade2black, Kaveh, cody Nov 27 '17 at 1:52

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I find it hard to follow what your question is because you've just given us a bunch of links and some code. The code doesn't really seem relevant, whereas the links contain vital information about what problem you're actually trying to solve. Isn't the direction of solution directly given by the recurrences you use to build up the DP table? $\endgroup$ – David Richerby Nov 21 '17 at 10:40
3
$\begingroup$

If a cell depends on cells to its left and bottom, the solution should start at the bottom-left. And so on for all other combinations of left/right and top/bottom.

$\endgroup$
  • $\begingroup$ Can you explain how you would think about Dungeon Game problem then? Would you think "well I need to get to the bottom-right, so start at the bottom-right" or would you think "well I can only move right and down, so the current cell depends on whether I came from the top or left, so start top-left"? The Coin Collecting problem works if you start at either top-left or bottom-right, but I haven't been able to come up with a solution for Dungeon Game that started top-left. $\endgroup$ – atkayla Nov 18 '17 at 0:27
  • $\begingroup$ It's not about the problem, it's about the recursion formula. $\endgroup$ – Yuval Filmus Nov 18 '17 at 4:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.