题目说人话

• 一个R*C的花生地（矩阵）
• 开始位置(1， 1)， 终点位置(R，C)
• 每次只能往右走或者往下走，每到一个位置都会获得花生a[i][j]
• 求走完整个花生地所获得的最大的花生个数

输入

• 第一行输入T，表示测试组数
• 每组输入R，C，表示矩阵大小
• 每组按行输入每个位置的花生数a[i][j]

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出

• T组数据，每组一个整数，表示走完花生地能够获得的最多花生数

8
16

算法 (dp) $O(n^2)$

• 状态表示：f[i][j]：表示走到位置(i，j)能获得的花生总和
• 状态属性：花生总和的最大值
• 状态计算：每个位置(i，j)只能从其左侧(i-1，j)或者上侧(i，j-1)到达，因此
  f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j]
• 边界处理:i==1 and j==1时为起点，没有前置位置，i==1时该位置只能从左侧到达，j==1时该位置只能从上侧到达

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 109;
int a[N][N], f[N][N];

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        memset(f, 0, sizeof f);
        int R, C;
        cin >> R >> C;
        for(int i=1; i<=R; i++)
            for(int j=1; j<=C; j++)
                cin >> a[i][j];
        for(int i=1; i<=R; i++)
            for(int j=1; j<=C; j++)
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
        cout << f[R][C] << endl;
    }
    return 0;
}