The trick here is to name the state correctly, then let the implementation follow. For 174. Dungeon Game, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, binary search, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- WA
- 30 / 45 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are calculateMinimumHP, isReachable.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//WA
02//30 / 45 test cases passed.
03class Solution {
04public:
05 int calculateMinimumHP(vector<vector<int>>& dungeon) {
06 int m = dungeon.size();
07 int n = dungeon[0].size();
08
09 vector<vector<int>> hp = dungeon, minhp = dungeon;
10
11 for(int row = 1; row < m; ++row){
12 hp[row][0] += hp[row-1][0];
13 minhp[row][0] = min(minhp[row-1][0], hp[row][0]);
14 }
15
16 for(int col = 1; col < n; ++col){
17 hp[0][col] += hp[0][col-1];
18 minhp[0][col] = min(minhp[0][col-1], hp[0][col]);
19 }
20
21 for(int row = 1; row < m; ++row){
22 for(int col = 1; col < n; ++col){
23 /*
24 starts from position with higher minhp
25 if minhp are the same, comes from higher hp
26 but this algorithm will fail on example like:
27 [[1,-3,3],
28 [0,-2,0],
29 [-3,-3,-3]]
30 because when we are at (1,2), it will choose to
31 start from (1,1), but actually start from (0,2)
32 give us higher hp
33 1 -2 1
34 1 -1 -1
35 -2 -4 -4
36 (hp)
37
38 1 -2 -2
39 1 -1 -1
40 -2 -4 -4
41 (minhp)
42 */
43 if(minhp[row-1][col] > minhp[row][col-1]){
44 //accumulated hp
45 hp[row][col] += hp[row-1][col];
46 //minimum hp until now
47 minhp[row][col] = min(hp[row][col], minhp[row-1][col]);
48 }else if(minhp[row-1][col] < minhp[row][col-1]){
49 hp[row][col] += hp[row][col-1];
50 minhp[row][col] = min(hp[row][col], minhp[row][col-1]);
51 }else if(hp[row-1][col] >= hp[row][col-1]){
52 hp[row][col] += hp[row-1][col];
53 minhp[row][col] = min(hp[row][col], minhp[row-1][col]);
54 }
55 }
56 }
57
58 for(int row = 0; row < m; ++row){
59 for(int col = 0; col < n; ++col){
60 cout << dungeon[row][col] << " ";
61 }
62 cout << endl;
63 }
64
65 for(int row = 0; row < m; ++row){
66 for(int col = 0; col < n; ++col){
67 cout << hp[row][col] << " ";
68 }
69 cout << endl;
70 }
71
72 for(int row = 0; row < m; ++row){
73 for(int col = 0; col < n; ++col){
74 cout << minhp[row][col] << " ";
75 }
76 cout << endl;
77 }
78
79 return (minhp[m-1][n-1] <= 0) ? (-minhp[m-1][n-1]+1) : 1;
80 }
81};
82
83//DP, top-bottom(starts from right-bottom corner)
84//https://leetcode.com/problems/dungeon-game/discuss/698271/Python-Short-DP-7-lines-O(mn)-top-down-explained
85//Runtime: 12 ms, faster than 83.36% of C++ online submissions for Dungeon Game.
86//Memory Usage: 9.2 MB, less than 13.19% of C++ online submissions for Dungeon Game.
87//time: O(mn), space: O(mn)
88class Solution {
89public:
90 int calculateMinimumHP(vector<vector<int>>& dungeon) {
91 int m = dungeon.size();
92 int n = dungeon[0].size();
93
94 //padding to the bottom and to the right
95 vector<vector<int>> minhp(m+1, vector<int>(n+1, INT_MAX));
96
97 /*
98 (m,n-1) and (m-1, n) is the bottom neighbor and
99 right neighbor of princess
100 */
101 minhp[m][n-1] = minhp[m-1][n] = 1;
102
103 for(int i = m-1; i >= 0; --i){
104 for(int j = n-1; j >= 0; --j){
105 if(dungeon[i][j] - min(minhp[i+1][j], minhp[i][j+1]) >= 0){
106 /*
107 we need min(minhp[i+1][j], minhp[i][j+1]) hp
108 so that we can survive if we go to (i+1,j) or (i,j+1).
109
110 dungeon[i][j] - min(minhp[i+1][j], minhp[i][j+1]) means
111 when we are at (i,j), we get dungeon[i][j] hp,
112 and when we go to (i+1,j) or (i,j+1),
113 we will use min(minhp[i+1][j], minhp[i][j+1]) hp
114
115 if this number >= 0, that means we can survive at (i,j) with
116 minimum possible hp, which is 1
117 */
118 minhp[i][j] = 1;
119 }else{
120 /*
121 at (i,j), our hp is dungeon[i][j],
122 (since the algorithm starts from bottom-right,
123 we don't consider the cells before (i,j)),
124 when we go to (i+1,j) or (i,j+1),
125 we remain dungeon[i][j] - min(minhp[i+1][j], minhp[i][j+1])
126
127 minhp[i+1][j]: we need this hp to survive at (i+1,j)
128 minhp[i][j+1]: we need this hp to survive at (i,j+1)
129
130 min(minhp[i+1][j], minhp[i][j+1]) -dungeon[i][j]:
131 we need this hp to survive at (i,j)
132 */
133
134 //signed integer overflow
135 // minhp[i][j] = min(minhp[i+1][j]-dungeon[i][j],
136 // minhp[i][j+1]-dungeon[i][j]);
137
138 minhp[i][j] = min(minhp[i+1][j], minhp[i][j+1])-dungeon[i][j];
139 }
140 }
141 }
142
143 return minhp[0][0];
144 }
145};
146
147//DP, cleaner
148//https://leetcode.com/problems/dungeon-game/discuss/698271/Python-Short-DP-7-lines-O(mn)-top-down-explained
149//Runtime: 12 ms, faster than 83.36% of C++ online submissions for Dungeon Game.
150//Memory Usage: 9 MB, less than 55.57% of C++ online submissions for Dungeon Game.
151class Solution {
152public:
153 int calculateMinimumHP(vector<vector<int>>& dungeon) {
154 int m = dungeon.size();
155 int n = dungeon[0].size();
156
157 //padding to the bottom and to the right
158 vector<vector<int>> minhp(m+1, vector<int>(n+1, INT_MAX));
159
160 /*
161 (m,n-1) and (m-1, n) is the bottom neighbor and
162 right neighbor of princess
163 */
164 minhp[m][n-1] = minhp[m-1][n] = 1;
165
166 for(int i = m-1; i >= 0; --i){
167 for(int j = n-1; j >= 0; --j){
168 minhp[i][j] = max(
169 min(minhp[i+1][j], minhp[i][j+1]) - dungeon[i][j],
170 1);
171 }
172 }
173
174 return minhp[0][0];
175 }
176};
177
178//binary search, DP
179//https://leetcode.com/problems/dungeon-game/discuss/698212/Java-Binary-search-on-answer-and-check-if-true
180//Runtime: 40 ms, faster than 5.21% of C++ online submissions for Dungeon Game.
181//Memory Usage: 11.8 MB, less than 5.33% of C++ online submissions for Dungeon Game.
182class Solution {
183public:
184 int m, n;
185 bool isReachable(vector<vector<int>>& dungeon, int initial_hp){
186 //padding left and top
187 vector<vector<int>> hp(m, vector<int>(n));
188
189 hp[0][0] = dungeon[0][0] + initial_hp;
190
191 for(int i = 0; i < m; ++i){
192 for(int j = 0; j < n; ++j){
193 /*
194 we can come from (i-1,j) if we survive at (i-1,j),
195 i.e. hp[i-1][j] > 0
196 */
197 hp[i][j] = max({hp[i][j],
198 (i > 0 && hp[i-1][j] > 0) ? hp[i-1][j] + dungeon[i][j] : 0,
199 (j > 0 && hp[i][j-1] > 0) ? hp[i][j-1] + dungeon[i][j] : 0});
200 }
201 }
202
203 return hp[m-1][n-1] > 0;
204 };
205
206 int calculateMinimumHP(vector<vector<int>>& dungeon) {
207 m = dungeon.size();
208 n = dungeon[0].size();
209
210 int left = 1, right = 0;
211 int mid;
212
213 for(int i = 0; i < m; ++i){
214 for(int j = 0; j < n; ++j){
215 if(dungeon[i][j] < 0){
216 right += (-dungeon[i][j]);
217 }
218 }
219 }
220 ++right;
221
222 //find left boundary
223 while(left <= right){
224 mid = left + (right - left)/2;
225
226 if(isReachable(dungeon, mid)){
227 right = mid-1;
228 }else{
229 left = mid+1;
230 }
231 }
232
233 return left;
234 }
235};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.