# 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[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)

• 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