Skip to content

Latest commit

 

History

History
37 lines (31 loc) · 1 KB

174.dungeon-game.md

File metadata and controls

37 lines (31 loc) · 1 KB

算法思路

数字三角形模型 DP

$f[i][j]$ 表示从 $i,j$ 到达右下角所需要的最小体力值

代码实现

class Solution {
    public int calculateMinimumHP(int[][] w) {
        int m = w.length, n = w[0].length;
        int[][] f=  new int[m][n];
        for (int i =0;i< m; i++)
            for (int j=0; j<n; j++) f[i][j] = Integer.MAX_VALUE;

        for (int i = m-1; i>=0; i--){
            for (int j = n-1; j >=0; j--){
                if (i == m-1 && j == n-1){
                    f[i][j] = Math.max(1, 1 - w[i][j]);
                    continue;
                }
                if (i + 1< m) { // 可以到达 i+1,j
                    f[i][j] = f[i+1][j] - w[i][j];
                }
                if (j+1< n){
                    f[i][j] = Math.min(f[i][j], f[i][j+1] - w[i][j]);
                }
                f[i][j] = Math.max(1, f[i][j]);
            }
        }
        return f[0][0];
    }
}