Dungeon Game
题目大意：公主被困在迷宫的右下角，骑士初始位于迷宫的左上角。迷宫的每个单元格（包括左上角和右下角）都有一个整数值x，如果x < 0，骑士到达该单元格时掉|x|的血；如果x > 0骑士在该单元格加|x|的血；如果 x == 0，骑士的血不掉也不加。如果骑士的血为0，那么他马上死亡。
要使骑士活着见到公主，那么骑士出发时最少需要加多少血。
https://leetcode.com/submissions/detail/32832133/
如果按照常规思维，从左上角到右下角的计算顺序，需要保存到某个单元格时最少需要的血以及剩下的血。如果逆向思维一下，从右下角向左上角计算，如果单元格需要更多的血，就加上需要的血；否则减去当前需要的血值。这种思维方式可以简化解题思路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int calculateMinimumHP(int[][] d) {
if(d == null || d.length == 0 || d[0].length == 0) return 1;
int[][] dp = new int[d.length][d[0].length];
for(int i = d.length - 1; i >= 0; --i) {
for(int j = d[0].length - 1; j >= 0; --j) {
if(i == d.length - 1 && j == d[0].length -1)
dp[i][j] = Math.max(1, 1 - d[i][j]);
else if(i == d.length - 1)
dp[i][j] = Math.max(1, dp[i][j + 1] - d[i][j]);
else if(j == d[0].length - 1)
dp[i][j] = Math.max(1, dp[i + 1][j] - d[i][j]);
else
dp[i][j] = Math.max(1, Math.min(dp[i][j + 1], dp[i + 1][j]) - d[i][j]);
}
}
return dp[0][0];
}
|
Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
https://leetcode.com/problems/triangle/
1
2
3
4
5
6
7
8
9
10
11
| public int minimumTotal(List<List<Integer>> tri) {
if(tri == null || tri.size() == 0) return 0;
int len = tri.get(tri.size() - 1).size();
int[] dp = new int[len + 1];
for(int i = len - 1; i >= 0; --i) {
List<Integer> list = tri.get(i);
for(int j = 0; j < list.size(); ++j)
dp[j] = list.get(j) + Math.min(dp[j], dp[j + 1]);
}
return dp[0];
}
|