题解 | 龙与地下城游戏问题-从终点开始倒推每一个点的最低生命值

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                map[i][j] = in.nextInt();

        int[][] dp = new
        int[n][m]; //dp[i][j] 表示从i,j走到终点所需的最低血量

        dp[n - 1][m - 1] = Math.max(1 - map[n - 1][m - 1], 1);

        for (int i = n - 2; i >= 0; i--) {
            dp[i][m - 1] = Math.max(dp[i + 1][m - 1] - map[i][m - 1], 1);
        }
        for (int j = m - 2; j >= 0; j--) {
            dp[n - 1][j] = Math.max(dp[n - 1][j + 1] - map[n - 1][j], 1);
        }

        //更新剩余dp
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                int nextMinSelect = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(nextMinSelect - map[i][j], 1);
            }
        }

        System.out.println(dp[0][0]);
    }
}