# When solving dynamic programming in a grid, how do you recognize whether the solution should start at the bottom-right of the table or top-left? [closed]

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.length;

var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
hp = 1;
hp = 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.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;
}

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


## closed as unclear what you're asking by David Richerby, Evil, fade2black, Kaveh, codyNov 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.

• 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? – David Richerby Nov 21 '17 at 10:40