【题解】采摘花生2
【题目描述】
Hello Kitty又一次来到花生地里摘花生，从左上角进入花生地，从右下角出去，只能向右或者向下，请问Hello Kitty应该沿着什么样的路线走，能够摘到的花生数量最多（假设花生地里没有任何2株的花生一样多，也不存在多条路线能够摘到一样多的花生的情况）？
比如输入：
2 2
1 2
3 4
应该输出：1-3-4，也就是按照1 3 4这三株数量的花生摘过去，能够摘到最多的花生！
【输入描述】
第一行是2个整数m和n（2=<m,n<=100），代表花生地有m行，n列花生！
后面m行，每行有n个整数代表了每行中，每株花生的数量
【输出描述】
输出Hello Kitty按照走过的路线中，摘到每株花生的数量。
【样例输入】
2 2 1 2 3 4
【样例输出】
1-3-4
【题目分析】
在 花生采摘题目基础之上修改的。
【参考答案】
#include <iostream>
using namespace std;
const int MAX = 100;
int w[MAX][MAX]; // 花生数量
int f[MAX][MAX]; // 最大花生数量
int path[MAX][MAX]; // 记录路径方向，0表示从上方，1表示从左方
void printPath(int i, int j) {
if (i == 0 && j == 0) {
cout << w[i][j];
return;
}
if (path[i][j] == 0) {
printPath(i - 1, j);
} else {
printPath(i, j - 1);
}
cout << "-" << w[i][j];
}
int main() {
int r, c;
cin >> r >> c;
// 输入花生数量
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> w[i][j];
}
}
// 初始化起点
f[0][0] = w[0][0];
// 动态规划计算最大花生数量
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i == 0 && j == 0) continue; // 起点已初始化
if (i == 0) {
// 第一行只能从左方移动过来
f[i][j] = f[i][j - 1] + w[i][j];
path[i][j] = 1; // 从左方
} else if (j == 0) {
// 第一列只能从上方移动过来
f[i][j] = f[i - 1][j] + w[i][j];
path[i][j] = 0; // 从上方
} else {
// 其他情况，选择上方或左方中较大的
if (f[i - 1][j] > f[i][j - 1]) {
f[i][j] = f[i - 1][j] + w[i][j];
path[i][j] = 0; // 从上方
} else {
f[i][j] = f[i][j - 1] + w[i][j];
path[i][j] = 1; // 从左方
}
}
}
}
// 输出路径
printPath(r - 1, c - 1);
cout << endl;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
