链接：https://www.nowcoder.com/acm/contest/130/B
来源：牛客网
第一行一个整数T表示数据的组数。(1 ≤ T ≤ 20)
对于每组数据：
第一行两个整数n，m表示棋盘的规格。(1 ≤ n, m ≤ 500)
接下来n行每行m个整数aij表示方格对应的分数。(
)
对于每组数据输出一行表示答案。
2
思路分析 ： 两个方向，第一个是考虑记忆化的搜索，对于一个位置很容易判断出来，他是先走的人走的还是后走的人走的，先走的人下一个位置一定是选小的，后走的人下一步一定是选大的。
代码示例：
const int inf = 0x3f3f3f3f;
int n, m;
int mp[505][505];
int dp[505][505];
int dfs(int x, int y){
if (dp[x][y] != inf) return dp[x][y];
if ((x+y)%2 == 0){
if (x == n && y == m) return dp[x][y] = mp[x][y];
int res = inf;
if (x < n) res = min(res, dfs(x+1, y));
if (y < m) res = min(res, dfs(x, y+1));
return dp[x][y] = mp[x][y]+res;
}
else {
if (x == n && y == m) return dp[x][y] = -mp[x][y];
int res = -inf;
if (x < n) res = max(res, dfs(x+1, y));
if (y < m) res = max(res, dfs(x, y+1));
return dp[x][y] = res-mp[x][y];
}
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int t;
cin >> t;
while(t--){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = inf;
scanf("%d", &mp[i][j]);
}
}
//memset(dp, inf, sizeof(dp));
int ans = dfs(1, 1);
printf("%d\n", ans);
//printf("+++ %d %d %d %d \n", dp[1][1], dp[1][2], dp[2][1], dp[2][2]);
}
return 0;
}
思路二 ：考虑dp
dp[i][j]表示以 i, j 为起点到达终点的答案的最大值，但是要注意的是从终点往回去推
代码示例：
const int inf = 0x3f3f3f3f;
int n, m;
int mp[505][505];
int dp[505][505];
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int t;
cin >>t;
while(t--){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &mp[i][j]);
}
}
//memset(dp, 0, sizeof(dp));
for(int i = n; i >= 1; i--){
for(int j = m; j >= 1; j--){
if (i == n && j == m) dp[i][j] = mp[i][j];
else if (i == n) dp[i][j] = mp[i][j]-dp[i][j+1];
else if (j == m) dp[i][j] = mp[i][j]-dp[i+1][j];
else {
dp[i][j] = mp[i][j]-max(dp[i+1][j], dp[i][j+1]);
}
}
}
printf("%d\n", dp[1][1]);
}
return 0;
}
原文：https://www.cnblogs.com/ccut-ry/p/9251923.html