【题解】摘花生问题
【题目描述】
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只能向东或向南移动，使用动态规划解决这个问题。
状态定义：
设dp[i][j]表示从起点(0, 0)到达(i, j)时能够摘到的最大花生数量。状态转移方程：
如果
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]（从上面或左边来，取最大值）。最终结果：
对于每组数据，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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。