1、前言

2、思路

这道题咋一看好像直接能套 dfs 的套路把题目做出来，但是到达终点后，最后一个数是要特殊处理的，因为我们需要保证骑士在最后的格子需要活下来，那么最后一个格子需要特殊处理。如果数字为正，那没有什么用，直接返回0就行；如果数字为负，那么需要返回相应需要扣减的血量。

还有就是，普通的棋盘遍历都是求最大或者最小步数之类的，但是这里却行不通，不能单纯的求最大数或者最小的数，因为没啥意义。这题需要求最小消耗量，直接减每一步的消耗，负数直接加；正数直接减，但是减到0需要直接返回0。

3、代码

public class CalculateMinimumHP {

    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] memo = new int[m][n];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(dungeon, 0, 0, memo) + 1;
    }

    private int dfs(int[][] dungeon, int i, int j, int[][] memo) {
        if(i == dungeon.length - 1 && j == dungeon[0].length - 1){
            return dungeon[i][j] >= 0 ? 0 : -dungeon[i][j];
        }

        if(i >= dungeon.length || j >= dungeon[0].length){
            return Integer.MAX_VALUE;
        }

        if(memo[i][j] != - 1){
            return memo[i][j];
        }

        int res = Math.min(dfs(dungeon, i  + 1, j, memo), dfs(dungeon, i, j + 1, memo))  -  dungeon[i][j];
        memo[i][j] = res <= 0 ? 0 : res;

        return memo[i][j];
    }


    public static void main(String[] args) {
        int[][] dungeon = {
                {-1, -5},
                {-4, -3}
        };
        System.out.println(new CalculateMinimumHP().calculateMinimumHP(dungeon));
    }
}