摘花生
首先，我们知道，对于每一个点，它只能从上面或左边转移而来。
那么，对于这一个点，我们当然会选取上面和左边中价值最大的进行转移。
所以，我们可以设定一个二维数组：int f[110][110]，存储从a1,1到ax,y的最大价值。
状态转移方程就是：fx,y=max(fx−1,y,fx,y−1)+ax,y
最后献上代码：（我的代码没有开f数组，是边读入边处理的，直接在a数组上进行修改）
#include <bits/stdc++.h>
using namespace std;
int T, a[110][110], n, m;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1;i <= n; i++)
for (int j = 1;j <= m; j++) {
scanf ("%d", &a[i][j]);
a[i][j] += max(a[i - 1][j], a[i][j - 1]);
}
printf("%d\n", a[n][m]);
}
return 0;
}
运行时间336ms
为什么最后输出a[ i ] [ j ]不对呢，到最后输出的i，j不就相当于n，m了吗
因为i，j是循环中的变量，也就是局部变量。
出了循环就消失了，也就是在循环外不能使用。
你是代码CE吗？
没有 就是调试的时候结果结果为0
把i j定义到循环外也不对
代码在这里发一下，代码前后记得要加上```
#include<cstdio> #include<iostream> using namespace std; const int N=1010; int arr[N][N]; int main() { int T; int r,c; scanf("%d",&T); while(T--) { scanf("%d %d",&r,&c); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { scanf("%d",&arr[i][j]); } for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { arr[i][j]=max(arr[i-1][j]+arr[i][j],arr[i][j-1]+arr[i][j]);//动态规划模板（取两种情况的最大值） } printf("%d\n",arr[r][c]); } return 0; }这不是对的吗？AC了呀
#include<cstdio> #include<iostream> using namespace std; const int N=1010; int arr[N][N]; int main() { int T; int i,j; int r,c; scanf("%d",&T); while(T--) { scanf("%d %d",&r,&c); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { scanf("%d",&arr[i][j]); } for(i=1;i<=r;i++) for(j=1;j<=c;j++) { arr[i][j]=max(arr[i-1][j]+arr[i][j],arr[i][j-1]+arr[i][j]);//动态规划模板（取两种情况的最大值） } printf("%d\n",arr[i][j]); } return 0; }复制错了不好意思
我懂了，你的后面的双重循环，当i>r && j>c的时候停止，这个时候i == r + 1，j == c + 1
所以应该减一
改为这样
#include<cstdio> #include<iostream> using namespace std; const int N=1010; int arr[N][N]; int main() { int T; int i,j; int r,c; scanf("%d",&T); while(T--) { scanf("%d %d",&r,&c); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) { scanf("%d",&arr[i][j]); } for(i=1;i<=r;i++) for(j=1;j<=c;j++) { arr[i][j]=max(arr[i-1][j]+arr[i][j],arr[i][j-1]+arr[i][j]);//动态规划模板（取两种情况的最大值） } printf("%d\n",arr[i - 1][j - 1]); } return 0; }对哦 明白了 多谢