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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minInitialHealth(vector<vector<int>>& map) {
    int n = map.size();
    int m = map[0].size();
    vector<vector<int>> dp(n, vector<int>(m));
    
    // 初始化终点
    dp[n-1][m-1] = max(1, 1 - map[n-1][m-1]);
    
    // 初始化最后一列
    for(int i = n-2; i >= 0; i--) {
        dp[i][m-1] = max(1, dp[i+1][m-1] - map[i][m-1]);
    }
    
    // 初始化最后一行
    for(int j = m-2; j >= 0; j--) {
        dp[n-1][j] = max(1, dp[n-1][j+1] - map[n-1][j]);
    }
    
    // 填充其他位置
    for(int i = n-2; i >= 0; i--) {
        for(int j = m-2; j >= 0; j--) {
            int minNext = min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = max(1, minNext - map[i][j]);
        }
    }
    
    return dp[0][0];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> map(n, vector<int>(m));
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    
    cout << minInitialHealth(map) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int minInitialHealth(int[][] map) {
        int n = map.length;
        int m = map[0].length;
        int[][] dp = new int[n][m];
        
        // 初始化终点
        dp[n-1][m-1] = Math.max(1, 1 - map[n-1][m-1]);
        
        // 初始化最后一列
        for(int i = n-2; i >= 0; i--) {
            dp[i][m-1] = Math.max(1, dp[i+1][m-1] - map[i][m-1]);
        }
        
        // 初始化最后一行
        for(int j = m-2; j >= 0; j--) {
            dp[n-1][j] = Math.max(1, dp[n-1][j+1] - map[n-1][j]);
        }
        
        // 填充其他位置
        for(int i = n-2; i >= 0; i--) {
            for(int j = m-2; j >= 0; j--) {
                int minNext = Math.min(dp[i+1][j], dp[i][j+1]);
                dp[i][j] = Math.max(1, minNext - map[i][j]);
            }
        }
        
        return dp[0][0];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] map = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        
        System.out.println(minInitialHealth(map));
        sc.close();
    }
}

def min_initial_health(map_grid):
    n, m = len(map_grid), len(map_grid[0])
    dp = [[0] * m for _ in range(n)]
    
    # 初始化终点
    dp[n-1][m-1] = max(1, 1 - map_grid[n-1][m-1])
    
    # 初始化最后一列
    for i in range(n-2, -1, -1):
        dp[i][m-1] = max(1, dp[i+1][m-1] - map_grid[i][m-1])
    
    # 初始化最后一行
    for j in range(m-2, -1, -1):
        dp[n-1][j] = max(1, dp[n-1][j+1] - map_grid[n-1][j])
    
    # 填充其他位置
    for i in range(n-2, -1, -1):
        for j in range(m-2, -1, -1):
            min_next = min(dp[i+1][j], dp[i][j+1])
            dp[i][j] = max(1, min_next - map_grid[i][j])
    
    return dp[0][0]

n, m = map(int, input().split())
map_grid = []
for _ in range(n):
    row = list(map(int, input().split()))
    map_grid.append(row)

print(min_initial_health(map_grid))