思路 二维DP
只能从坐标(i-1, j)或坐标(i, j-1)到达坐标(i,j),因此取这两种情况的最大值即可;
C++ 代码
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N];
int main() {
int k, m, n;
cin >> k;
while(k--) {
cin >> m >> n;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
for(int i = 1; i < n; i++) a[0][i] += a[0][i - 1];//初始化第一行
for(int i = 1; i < m; i++) a[i][0] += a[i - 1][0];//初始化第一列
//从第二行,第二列开始
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
a[i][j] = max(a[i - 1][j], a[i][j - 1]) + a[i][j];
}
}
printf("%d\n", a[m - 1][n - 1]);
}
return 0;
}