解题思路

Hello Kitty 从左上角进花生地，只能向右或向下走，从右下角出去，问摘到最多花生的路线。

思路：动态规划求最大和，再回溯路径。

1. DP 求最大花生数：到每个格子的最大花生数 = 这个格子的花生 + 上面和左边中更大的那个
2. 回溯路径：从终点往回走，每一步看是从上面来还是从左边来（谁贡献的 a 值大就走哪边），把经过的花生记下来
3. 逆序输出：回溯是从终点往起点，所以最后要反过来输出

举例：2×2 花生地

1 2
3 4

• 最优路径是 1-3-4，花生总数 8
• 从终点 4 往回：上面 3 比左边 2 大，走上面，路径 4←3←1
• 逆序输出 1-3-4

参考代码

#include <iostream>
using namespace std;

int c[105][105];
int a[105][105];

int main() {
    int m, n;
    cin >> m >> n;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> c[i][j];
            a[i][j] = c[i][j];
            if (a[i - 1][j] > a[i][j - 1]) {
                a[i][j] += a[i - 1][j];  // 从上面来更优
            } else {
                a[i][j] += a[i][j - 1];
            }
        }
    }

    // 回溯路径
    int path[205];
    int k = 0, x = m, y = n;
    while (x >= 1 && y >= 1) {
        path[k++] = c[x][y];
        if (a[x - 1][y] > a[x][y - 1]) x--;
        else y--;
    }

    for (int i = k - 1; i >= 0; i--) {  // 逆序输出
        if (i != 0) cout << path[i] << "-";
        else cout << path[i] << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(M×N)，DP 和回溯各一遍
• 空间复杂度：O(M×N)，存花生和 DP 值