题解 | #龙与地下城游戏问题#

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int [][]map=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j]=input.nextInt();
            }
        }
        int [][]dp=new int[n][m];
//         用hpMatrix表示骑士从任意一格到达终点所需要的最少血量
        dp[n-1][m-1]=(map[n-1][m-1]>0?1:-map[n-1][m-1]+1);
        for(int j=m-2;j>=0;j--){
            if(map[n-1][j]-dp[n-1][j+1]>=0){
                dp[n-1][j]=1;
            }
            else{
                dp[n-1][j]=dp[n-1][j+1]-map[n-1][j];
            }
        }
        for(int i=n-2;i>=0;i--){
            if(map[i][m-1]-dp[i+1][m-1]>=0){
                dp[i][m-1]=1;
            }
            else{
                dp[i][m-1]=dp[i+1][m-1]-map[i][m-1];
            }
        }
        for(int i=n-2;i>=0;i--){
            for(int j=m-2;j>=0;j--){
                int minNeed=Math.min(dp[i+1][j],dp[i][j+1]);   //两个方向最少需要的血
                if(map[i][j]-minNeed>=0){  //同样的思路，如果够用，那就只需要1点血进来，因为最少一点血
                    dp[i][j]=1;
                }
                else{
                    dp[i][j]=minNeed-map[i][j]; //如果不够用的话，就只能增加进来时候的血
                }
            }
        }
        System.out.println(dp[0][0]);
    }
}