I've been trying to solve this problem by finding the shortest path. I've tried Dijkstra algorithm and Bellman-Ford algorithm. Neither of them works. Haven't tried A*, but I really doubt it works.
I wonder if there's any solution using any of the shortest path algorithm. Why they don't suppose to work? Please let me know you thought.
BTW, here's my 7 lines Python DP:
def calculateMinimumHP(self, dungeon): n, m = len(dungeon), len(dungeon) f = [1 << 64] * (n + 1) f[n - 1] = 1 for i in xrange(m - 1, -1, -1): for j in xrange(n - 1, -1, -1): f[j] = max(min(f[j], f[j + 1]) - dungeon[i][j], 1) return f
How did you implement Dijkstra? It seems like it should work by utilizing a priority queue that tracks the current health and prioritizes by the lowest minimum health seen so far.
It wouldn't really be "shortest path", though, as that's not what we're looking for, and Dijkstra doesn't work for that anyways when we have negative paths.