【题目描述】

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;  }