解题思路

Hello Kitty 从花生地的左上角走到右下角，每次只能向右或向下走，经过的格子上的花生都能摘走，问最多能摘多少。

这是一个经典的动态规划题。

核心思想：

到某个格子时，只能从它的上面或左边走过来。那么到这个格子的最大花生数 = 这个格子的花生 + 上面和左边两个格子中更大的那个。

步骤：

1. 从上到下、从左到右遍历每个格子
2. 对每个格子，比较它上面的累计值和左边的累计值
3. 取更大的那个，加上当前格子的花生数，就是到这里的最大花生数
4. 最后右下角的值就是答案

为什么只比较上面和左边？ 因为只能向右和向下走，所以到 (i,j) 只能从 (i-1,j) 或 (i,j-1) 来。

举例 2×2 花生地：

1 1
3 4

• 从左上 1 出发
• 向下到 3：1+3=4；向右到 1：1+1=2
• 到右下角：4 的上方是 1（已算成2），左边是 3（已算成4），取大的 4 + 当前 4 = 8
• 路径 1→3→4，最多 8 颗

参考代码

#include <iostream>
using namespace std;

int a[110][110];

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

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; 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];  // 从左边来更优
            }
        }
    }

    cout << a[m][n];
    return 0;
}

复杂度分析

• 时间复杂度：O(M×N)，每个格子算一次
• 空间复杂度：O(M×N)，二维数组存花生