/ 本题dp可解毫无疑问；本人较懒就用了二分答案+dfs判断的方式。从题意易知起始的大小与路径中最小值最大的情况成正比，故而枚举答案，复杂度O（logn）,对于每次枚举判断是否可行，即路径中存在一条路恒>0，复杂度O(n).这样一来综合复杂度O(nlogn),n=1e6,故而可解。 /

include <iostream>

include <cstring>

include <string>

int b[1001][1001],a[1001][1001],c[1001][1001],n,m;
void dfs(int x,int y)
{
if(x>n||y>m||a[x][y]<=0||c[x][y])return;
c[x][y]=1;
dfs(x+1,y);
dfs(x,y+1);
}
int main()
{
std::cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)std::cin>>b[i][j];

int l=1,r=1e9,mid,g=1e9;

while(l<=r)
{
    int mid=(l+r)/2;
    std::memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=b[i][j];
    a[1][1]+=mid;

    for(int i=2;i<=m;i++)a[1][i]+=a[1][i-1];
    for(int j=2;j<=n;j++)a[j][1]+=a[j-1][1];

    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)a[i][j]+=std::max(a[i-1][j],a[i][j-1]);
    dfs(1,1);
    if(c[n][m])
    {
        g=std::min(g,mid);
        r=mid-1;
    }
    else l=mid+1;
}
std::cout<<g<<std::endl;

}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[][] vals = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vals[i][j] = in.nextInt();
            }
        }
        int[][] dp = new int[m+1][n+1];
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                dp[i][j] = Math.min(Math.max(1, dp[i+1][j]), Math.max(1, dp[i][j+1])) - vals[i][j];
            }
        }
        dp[0][0] = dp[0][0] > 0 ? dp[0][0] : 1;
        System.out.println(dp[0][0]);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int m = Integer.parseInt(strs[0]), n = Integer.parseInt(strs[1]);
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            strs = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(strs[j]);
            }
        }

        int[][] dp = new int[m + 1][n + 1];
        dp[m][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j]);
            }
        }
        System.out.println(dp[0][0]);
    }
}

【关键点】角色的三种状态：

1. 角色在(i, j)之前（即在(i-1, j)或者(i, j-1)，下一步即将移动到(i, j)）行动力用dp[i][j]表示，比如初始行动力为dp[0][0]，下一步即将移动到(0, 0)；

2. 角色在(i, j)时（下一步即将移动到(i+1, j)或者(i, j+1)）行动力等于dp[i][j]+a[i][j]，比如初始行动力为dp[0][0]，角色在(0, 0)时行动力为dp[0][0]+a[0][0]；

3. 角色在(i, j)之后（即在(i+1, j)或者(i, j+1)，上一步在(i, j)），此时有min(dp[i+1][j], dp[i][j+1])等于dp[i][j]+a[i][j]。

【分析】dp[i][j]表示角色尚在格子(i, j)之前并且即将要移动到格子(i, j)时的行动力。

dp[0][0]表示初始的行动力。

当行动力小于或者等于0时游戏失败，dp[i][j]必然大于或者等于(对应递推公式的max)1，即dp[i][j]>=1。

dp[i][j]+a[i][j]表示角色在格子(i, j)但尚未往下移动时的行动力，此时行动力为min(dp[i+1][j], dp[i][j+1])，采用min是因为最后要求的是最小值。

最后求解初始时刻的行动力，则应该从后往前推理，可得，

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    vector<vector<int> > a(m,vector<int>(n,0));
    vector<vector<int> > dp(m+1,vector<int>(n+1,0));
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            cin>>a[i][j];
    for(int i=m-1;i>=0;--i)
        for(int j=n-1;j>=0;--j)
            dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-a[i][j]);
    cout<<dp[0][0]<<endl;
    return 0;
}

#写一个python版的答案

#读取数据
m,n = map(int,input().split())
array = []
for _ in range(m):
    list1 = list(map(int,input().split()))
    array.append(list1)
#构建一个辅助数组，记录移动方向
#1表示竖直移动，0表示水平移动
line = [[0]*n for _ in range(m)]
for j in range(n-1):
    array[0][j+1] += array[0][j]
for i in range(m-1):
    array[i+1][0] += array[i][0]
#动态规划算每个点最小的体力值
for i in range(1,m):
    for j in range(1,n):
        if(array[i-1][j] > array[i][j-1]):
            array[i][j] += array[i-1][j]
            line[i][j] = 1
        else:
            array[i][j] += array[i][j-1]
#print(array)
#从右下角 往 左上角 回溯。 求得最小值
list1 = []
i = m-1
j = n-1
while(i>0 and j>0):
    if(line[i][j] == 1):
        i -= 1
    else:
        j -= 1
    list1.append(array[i][j])
if(i>0):
    for k in range( i):
        list1.append(array[k][0])
else:
    for k in range( j):
        list1.append(array[0][k])
#print(list1)
res = min(list1)
print(max(-res+1,1))

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    arr[i][j]=sc.nextInt();
                }
            }
            int[][] dp = new int[n][m];
            dp[n-1][m-1]=1;
            for(int i=n-2;i>=0;i--){
                dp[i][m-1]=Math.max(1,dp[i+1][m-1]-arr[i][m-1]);
            }
            for(int i=m-2;i>=0;i--){
                dp[n-1][i]=Math.max(1,dp[n-1][i+1]-arr[n-1][i]);
            }
            for(int i=n-2;i>=0;i--){
                for(int j=m-2;j>=0;j--){
                    dp[i][j]=Math.max(1,Math.min(dp[i+1][j],dp[i][j+1])-arr[i][j]);
                }
            }
            System.out.println(dp[0][0]);
        }
    }
}

#include<iostream>
using namespace std;
const int N = 1010, M = 1010;
int a[N][M], dp[N][M];
int n,m;
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> a[i][j];
    
    
    for(int i = n - 1; i >= 0; --i)
        for(int j = m - 1; j >= 0; --j)
            dp[i][j]= min(max(1,dp[i+1][j]-a[i][j]),max(dp[i][j+1]-a[i][j],1));
    
    cout << dp[0][0] << endl;
    
    return 0;
}

import sys
class Solution(object):
    def solveGrid(self,grid):
        self.M = len(grid) - 1  
        self.N = len(grid[0]) - 1
        self.dp = [[sys.maxint for j in range(self.N+1)] for i in range(self.M+1)]
        self.countPaths(grid, 1, 1, 1, [])
        return self.dp[self.M][self.N]

    def countPaths(self, grid, row, col, level, path):
        if path:
            path.append(path[-1] + grid[row][col])
        else:
            path.append(grid[row][col])
            
        tmp = max(1, -min(path) + 1)
        self.dp[row][col] = min(self.dp[row][col], tmp) 
        
        if row == self.M and col == self.N:
            return
        
        if col+1<=self.N \
        and tmp == self.dp[row][col] \
        and self.dp[row][col] < self.dp[row][col+1] \
        and self.dp[row][col] < self.dp[self.M][self.N]:
            self.countPaths(grid,row,col+1, level+1, path)
            path.pop()        
        
        if  row+1<=self.M \
        and tmp == self.dp[row][col] \
        and self.dp[row][col] < self.dp[row+1][col] \
        and self.dp[row][col] < self.dp[self.M][self.N]:
            self.countPaths(grid,row+1,col, level+1, path)
            path.pop()

if __name__ == "__main__":
    line = raw_input()
    lines = line.split()
    M, N = int(lines[0]), int(lines[1])
    grid = []
    grid.append([0 for j in range(N+1)])
    for _ in xrange(M):
        line = raw_input()
        lines = line.split()
        tmp = [0] + [int(item) for item in lines]
        grid.append(tmp)
    s = Solution()
    print s.solveGrid(grid)

A到吐血
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m;
int grid[1000][1000];
int ans;
void dfs(int x,int y,int temp,int w) {
    if (x<0||x>=m||y<0||y>=n) {
        return ;
    }
    if (y==n-1&&x==m-1) {
        temp=min(temp,w+grid[y][x]+temp);
        ans=max(temp,ans);
        return ;
    } else if (temp>ans) {
        int res1=w+grid[y][x];
        int res=temp;
        if (res1<=0) {
            res+=res1;
            res1=0;
        }
        //int res=min(temp,res1);
        dfs(x+1,y,res,res1);
        dfs(x,y+1,res,res1);
    }
}

int main() {
    while (cin>>n>>m) {
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                scanf("%d",&grid[i][j]);
            }
        }
        ans=-100000000;
        int temp=grid[0][0];
        dfs(0,0,0,0);
        //dfs(0,0,0,temp);
        cout<<abs(ans)+1<<endl;
    }
    return 0;
}