Write Code vs. Write Poetry: Dungeon Game (LeetCode Dynamic Programming)
Dungeon Game (LeetCode Dynamic Programming)
Question: The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Idea: With a few simple equations, we can solve this problem easily. Let us use dp[i][j] to denote the minimum health needed to start from block (i,j) (including entering (i,j)) then go to (m-1, n-1), where m is the number of rows, n is the number of columns. We have the following equations:
(1) dp[i][j]>=1, since dp[i][j] can not be 0 or below anytime, even before entering any block.
(2) dp[i][j]+dungeon[i][j]>=1, since the knight's health should be at least 1 after entering the block[i][j].
(3) dp[i][j]+dungeon[i][j]>=dp[i+1][j], since the knight's health should be enough to start from the block under [i][j]
(4) dp[i][j]+dungeon[i][j]>=dp[i][j+1], since the knight's health should be enough to start from the next block on the right of [i][j].
In any case, equation (1) and equation (2) are required to be fulfilled. However, either (3) or (4) works, the knight can succeed. By moving the items on the left of equations (1) - (4) except dp[i][j] to the right, we have
(5) dp[i][j]>=1
(6) dp[i][j]>=1- dungeon[i][j]
(7) dp[i][j]>= dp[i+1][j]-dungeon[i][j] OR dp[i][j+1]-dungeon[i][j].
Since we need to minimize the health needed, we take the minimum of the two routes in the equation (7). Then we have the final equation:
(8) dp[i][j]= maxOfThree(1, 1- dungeon[i][j], Math.min(dp[i+1][j]-dungeon[i][j], dp[i][j+1]-dungeon[i][j])).
For the dp blocks at dp[m-1][n-1], the last row and the last column, just remove the items out of the boundary.
Time: O(n^2) Space: O(n^2)
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Idea: With a few simple equations, we can solve this problem easily. Let us use dp[i][j] to denote the minimum health needed to start from block (i,j) (including entering (i,j)) then go to (m-1, n-1), where m is the number of rows, n is the number of columns. We have the following equations:
(1) dp[i][j]>=1, since dp[i][j] can not be 0 or below anytime, even before entering any block.
(2) dp[i][j]+dungeon[i][j]>=1, since the knight's health should be at least 1 after entering the block[i][j].
(3) dp[i][j]+dungeon[i][j]>=dp[i+1][j], since the knight's health should be enough to start from the block under [i][j]
(4) dp[i][j]+dungeon[i][j]>=dp[i][j+1], since the knight's health should be enough to start from the next block on the right of [i][j].
In any case, equation (1) and equation (2) are required to be fulfilled. However, either (3) or (4) works, the knight can succeed. By moving the items on the left of equations (1) - (4) except dp[i][j] to the right, we have
(5) dp[i][j]>=1
(6) dp[i][j]>=1- dungeon[i][j]
(7) dp[i][j]>= dp[i+1][j]-dungeon[i][j] OR dp[i][j+1]-dungeon[i][j].
Since we need to minimize the health needed, we take the minimum of the two routes in the equation (7). Then we have the final equation:
(8) dp[i][j]= maxOfThree(1, 1- dungeon[i][j], Math.min(dp[i+1][j]-dungeon[i][j], dp[i][j+1]-dungeon[i][j])).
For the dp blocks at dp[m-1][n-1], the last row and the last column, just remove the items out of the boundary.
Time: O(n^2) Space: O(n^2)
Read full article from Write Code vs. Write Poetry: Dungeon Game (LeetCode Dynamic Programming)
No comments:
Post a Comment