【题目描述】

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

【输入描述】

第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

【输出描述】

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

【样例输入】

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

【样例输出】

8
16

【数据范围】

1 ≤ T ≤ 100,
1 ≤ R, C ≤ 100,
0 ≤ M ≤ 1000

【题目分析】

在一个网格中寻找从左上角（西北角）到右下角（东南角）的路径，使得路径上的花生数量之和最大。Hello Kitty只能向东或向南移动，使用动态规划解决这个问题。

1. 状态定义：
   设 dp[i][j] 表示从起点 (0, 0) 到达 (i, j) 时能够摘到的最大花生数量。

2. 状态转移方程：

• 如果 i == 0 且 j == 0，dp[i][j] = grid[i][j]（起点）。

• 如果 i == 0，dp[i][j] = dp[i][j-1] + grid[i][j]（只能从左边来）。

• 如果 j == 0，dp[i][j] = dp[i-1][j] + grid[i][j]（只能从上面来）。

• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]（从上面或左边来，取最大值）。

3. 最终结果：
   对于每组数据，dp[R-1][C-1] 即为从起点到终点的最大花生数量。

【参考答案】

#include <bits/stdc++.h>
using namespace std;
int w[100][100], f[100][100];
int t, r, c;
int main () {
	cin >> t;
	while (t --) {
		cin >> r >> c;
		for (int i = 0; i < r; i ++) {
			for (int j = 0; j < c; j ++)
				cin >> w[i][j];
		}
		for (int i = 0; i < r; i ++) {
			for (int j = 0; j < c; j ++) {
				// 对第一行特判
				if (i == 0 && j != 0)
					f[i][j] = f[i][j - 1] + w[i][j];
				else {
					// 对第一列特判
					if (i != 0 && j == 0)
						f[i][j] = f[i - 1][j] + w[i][j];
					else
						// 其他情况
						f[i][j] = max(f[i][j - 1] + w[i][j], f[i - 1][j] + w[i][j]);
				}
			}
		}
		// 因为是从0开始的，所以最后都要减1
		cout << f[r - 1][c - 1] << endl;
	}
	return 0;
}