摘花生

题意

$T$ 组数据。 $R \times C$ 的花生地里，从西北角 $(1,1)$ 出发，只能向右或向下走到东南角 $(R,C)$ ，求经过格子花生数量之和的最大值。

思路

直接枚举所有路径是 $\binom{R+C-2}{R-1}$ 级别， $R=C=100$ 时不可行。先看一个可以验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-04 12:40
 * update_at: 2026-08-04 12:40
 */

// brute.cpp：小数据暴力解，使用选择序列递归枚举所有路径。
// 每一层递归在选择"下一步向右还是向下走"，走到底（到达 (r,c)）时结算并更新最优。
// 只能处理小数据：路径数是组合数 C(r+c-2, r-1)，指数级。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int r, c;                 // 行数、列数
int a[MAXN][MAXN];        // 花生数量
int ans;                  // 最优花生总数

// 当前在 (x, y)，已摘 sum 颗花生
void dfs(int x, int y, int sum) {
    if (x == r && y == c) {          // 到达东南角，结算
        ans = max(ans, sum);
        return;
    }
    if (x < r) dfs(x + 1, y, sum + a[x + 1][y]); // 向下走
    if (y < c) dfs(x, y + 1, sum + a[x][y + 1]); // 向右走
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        cin >> r >> c;
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                cin >> a[i][j];
            }
        }
        ans = 0;
        dfs(1, 1, a[1][1]);
        cout << ans << '\n';
    }
    return 0;
}

这个暴力把路线看成选择序列：每一层递归在选择"下一步向右还是向下"，到达 $(R,C)$ 就结算当前路径并更新最优。它正确但枚举了全部路径，路径数是组合数级。

关键观察：只能向右/向下走，所以每个格子 $(i,j)$ 只可能从上方 $(i-1,j)$ 或左方 $(i,j-1)$ 走来——走到它的最优路径，一定来自这两个格子中更优的那个。

定义 $dp[i][j]$ = 从 $(1,1)$ 走到 $(i,j)$ 能摘到的最大花生数：

dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + a[i][j]

边界 $dp[1][1] = a[1][1]$ ，答案就是 $dp[R][C]$ 。

以样例 2（ $3 \times 3$ ，花生数 [3 2 1; 2 1 2; 1 2 3]）走一遍转移表：

i \ j	1	2	3
1	3	3+2=5	5+1=6
2	3+2=5	max(5,5)+1=6	max(6,6)+2=8
3	5+1=6	max(6,5)+2=8	max(8,8)+3=11

看第 2 行第 3 列： $dp[2][3]$ 的两个候选是上方的 $dp[1][3]=6$ 和左方的 $dp[2][2]=6$ ，取较大者再加 $a[2][3]=2$ ，得到 8。逐格推进到 $dp[3][3]=11$ ，与样例一致（最优路径：右、右、下、下）。每个格子只依赖上、左两个已算好的前驱，这就是网格路径 DP 的全部结构。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-04 12:40
 * update_at: 2026-08-04 12:40
 */

/* AcWing 1015 摘花生 */
/* 网格路径 DP：从 (1,1) 只能向右/向下走到 (R,C)，每个格子只能从上方或左方走来，
 * dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int t;                    // 测试组数
int r, c;                 // 花生地行数、列数
int a[MAXN][MAXN];        // a[i][j]：位置 (i, j) 的花生数量
int dp[MAXN][MAXN];       // dp[i][j]：从 (1,1) 走到 (i,j) 能摘到的最大花生数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> r >> c;
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                cin >> a[i][j];
            }
        }

        // 起点边界：只有它自己
        dp[1][1] = a[1][1];
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (i == 1 && j == 1)
                    continue;
                // 从上方或左方走来，取较大者，再加上当前位置的花生
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
            }
        }

        cout << dp[r][c] << '\n';
    }
    return 0;
}

复杂度

每组数据 $O(RC)$ 时间、 $O(RC)$ 空间； $T$ 组总计 $O(TRC)$ 。

总结

“只能向右/向下"是网格 DP 的标志：它保证每个格子的前驱只有两个，状态转移直接由移动方向决定。和数字三角形（P1216）是同一个模型——三角里的"相邻两个"在这里变成"上方和左方”。

目录

题意

思路

代码

复杂度

总结