龙与地下城游戏问题

#include<bits/stdc++.h>
using namespace std;
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];
    int more = max(n, m), less = min(n, m);
	bool rowmore = more == n;
	vector<int>dp(less);
	int tmp = map[n - 1][m - 1], row = 0, col = 0;
	dp[less - 1] = tmp > 0 ? 1 : -tmp + 1;
	for (int j = less - 2; j >= 0; j--){
		row = rowmore ? more - 1 : j;
		col = rowmore ? j : more - 1;
		dp[j] = max(dp[j + 1] - map[row][col], 1);
	}
	int c1 = 0, c2 = 0;
	for (int i = more - 2; i >= 0; i--){
		row = rowmore ? i : less - 1;
		col = rowmore ? less - 1 : i;
		dp[less - 1] = max(dp[less - 1] - map[row][col], 1);
		for (int j = less - 2; j >= 0; j--){
			row = rowmore ? i : j;
			col = rowmore ? j : i;
			c1 = max(dp[j] - map[row][col], 1);
			c2 = max(dp[j + 1] - map[row][col], 1);
			dp[j] = min(c1, c2);
		}
	}
	cout<< dp[0];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int a[n][m];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    int dp[m+1];
    dp[m] = 1;
    for(int i=m-1;i>=0;i--)
        dp[i] = max(1, dp[i+1]-a[n-1][i]);
    dp[m] = INT_MAX;
    for(int i=n-2;i>=0;i--)
        for(int j=m-1;j>=0;j--)
            dp[j] = max(1, min(dp[j], dp[j+1]) - a[i][j]); 
    cout<<dp[0]<<endl;
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int arr[n][m], dp[n][m];
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < m; ++j) cin >> arr[i][j];
    // 时间复杂度O(NM)，空间复杂度O(NM)
    dp[n - 1][m - 1] = max(1 - arr[n - 1][m - 1], 1);
    for (int i = n - 2; i >= 0; --i) dp[i][m - 1] = max(dp[i + 1][m - 1] - arr[i][m - 1], 1);
    for (int j = m - 2; j >= 0; --j) dp[n - 1][j] = max(dp[n - 1][j + 1] - arr[n - 1][j], 1);
    for (int i = n - 2; i >= 0; --i) {
        for (int j = m - 2; j >= 0; --j) {
            dp[i][j] = min(max(dp[i + 1][j] - arr[i][j], 1), 
                           max(dp[i][j + 1] - arr[i][j], 1));
        }
    }
    cout << dp[0][0];
    return 0;
}

n , m = map(int , input().split())
map = []

for i in range(n):
    o = input().split()
    map.append(o)

for i in range(n):
    for j in range(m):
        map[i][j] = int(map[i][j])

for i in range(n-1,-1,-1):
    for j in range(m-1,-1,-1):
        if i == n-1 and j != m-1:
            map[i][j] = map[i][j+1] + map[i][j]
            
        elif i != n-1 and j == m-1:
            map[i][j] = map[i+1][j] + map[i][j]
        
        elif i != n-1 and j != m-1:
            map[i][j] = max(map[i][j+1] + map[i][j] , map[i+1][j] + map[i][j])
        
        if map[i][j] > 0:
            map[i][j] = 0
        
print(1-(map[0][0]))

#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;

// dp[i][j]: 从 i,j 位置进入需要拥有的血量
// dp[i][j]=max{1,min{dp[i+1][j]-a[i][j],dp[i][j+1]-a[i][j]}}
// dp[n-1][m-1]=max{1,1-a[n-1][m-1]}
// dp[x][y]=INF if x>=n&nbs***bsp;y>=m

int a[1009][1009];
int n,m;
int dp(int i,int j){
  if(i>=n||j>=m) return INF;
  if(i==n-1&&j==m-1) return max(1,1-a[n-1][m-1]);
  static int cache[1009][1009];
  if(cache[i][j]==0){
    cache[i][j]=max(1,min(dp(i+1,j)-a[i][j],dp(i,j+1)-a[i][j]));
  }
  return cache[i][j];
}

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }
  cout<<dp(0,0)<<endl;
}

def solution(nums, n, m):
    dp = [[0 for j in range(m)] for i in range(n)]
    dp[-1][-1] = max(1, 1 - nums[n - 1][-1])
    for i in range(2, n + 1):
        dp[-i][m - 1] = max(1, dp[-i + 1][m - 1] - nums[-i][m - 1])
    for j in range(2, m + 1):
        dp[n - 1][-j] = max(1, dp[n - 1][-j + 1] - nums[n - 1][-j])
    for i in range(2, n + 1):
        for j in range(2, m + 1):
            dp[-i][-j] = max(1, min(dp[-i + 1][-j], dp[-i][-j + 1]) - nums[-i][-j])
    return dp[0][0]


n, m = map(int, input().split())
nums = []
for i in range(n):
    nums.append(list(map(int, input().split())))
res = solution(nums, n, m)
print(res)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int aa = 0;
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] nums = new int[n][m];
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    nums[i][j] = in.nextInt(); 
                }
            }
            
            int[][] dp = new int[n+1][m+1];
            dp[n][m] = 1 - nums[n-1][m-1]  <= 0 ? 1 : 1 - nums[n-1][m-1];
            for(int i=n-1;i>0;i--) {
                if(nums[i-1][m-1] > 0) {
                    dp[i][m] = nums[i-1][m-1] - dp[i+1][m] >= 0 ? 1 : dp[i+1][m] - nums[i-1][m-1]; 
                } else if(nums[i-1][m-1] == 0) {
                    dp[i][m] = dp[i+1][m];
                } else {
                    dp[i][m] = -nums[i-1][m-1] + dp[i+1][m];
                }
            }
            
            for(int i=m-1;i>0;i--) {
                if(nums[i-1][m-1] > 0) {
                    dp[n][i] = nums[n-1][i-1] - dp[n][i+1] >= 0 ? 1 :  dp[n][i+1] - nums[n-1][i-1]; 
                }else if(nums[n-1][i-1] == 0) {
                    dp[n][i] = dp[n][i+1];;
                } else {
                    dp[n][i] = -nums[n-1][i-1] + dp[n][i+1];
                }
            }
            
            
            for(int i=n-1;i>0;i--) {
                for(int j=m-1;j>0;j--) {
                    int a = Math.min(dp[i+1][j],dp[i][j+1]);
                    if(nums[i-1][j-1] > 0) {
                        dp[i][j] = nums[i-1][j-1] - a >= 0 ? 1 : a - nums[i-1][j-1]; 
                    } else {
                        dp[i][j] = nums[i-1][j-1] == 0 ? a : -nums[i-1][j-1] + a;
                    }
                }
            }
            
            System.out.println(dp[1][1]);
        }
    }
}