dp-leetcode174

这道题还是花了点儿时间的,因为我一直在想着leetcode64 的解题思路,就一个劲的转牛角尖,以下是分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* leetcode 64 是从0 走向某一个最小的数
* leetcode 174 是从某一个数走向 1
* 开始的时候一直考虑是从左上角走到右下角,思路很混乱
*
* 逆向思维,
* 分析
* -10 1
* 30 -5 [start] 我们从start位置开始
* -5所在的位置走向start 时,显然需要携带6才可以保证到达start位置时大于等于1
* -5的前驱是 1 或者30 1-》6 显然在进入1处时最少携带5 30-》6 显然进入30时最少携带1便可
* 对于-10 如果向下(1)走,则需要携带11
* 如果向右(5)走 则需要携带15 当然我们要携带 11 而不是14
*
* 由此我们列出 状态转换式
* dp[i][j]=Math.max(Math.min(dp[i+1][j],dp[i][j-1])-dungeon[i][j],1);
*
* */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n=dungeon[0].length;
int [][] dp=new int[m+1][n+1];
for (int i = 0; i <m+1 ; i++) {
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
dp[m-1][n] = 1; // 以结束状态(右下角)为初始状态,而初始状态必须大于1(0的时候勇士不就死了),[0,0] 处为结束状态
for(int i = m-1; i>=0; i--)
{
for(int j =n-1; j>=0; j--)
{
int val = Math.min(dp[i+1][j], dp[i][j+1])-dungeon[i][j]; //目标数是最小数,所以在保证大于一的同时保持最小
dp[i][j] = Math.max(val, 1); //
}
}
return dp[0][0];
}