2088. 统计农场中肥沃金字塔的数目

发表于 分类于 阅读次数： Waline： 本文字数： 956 阅读时长 ≈ 3 分钟

考点

  • 子矩形DP

思路

一、问题描述

给定一个由 0/1 组成的二维矩阵 grid，其中：

  • 1 表示肥沃土地
  • 0 表示贫瘠土地

需要统计矩阵中所有肥沃金字塔与倒置肥沃金字塔的数量。

金字塔定义

  • 正金字塔： 顶点在上，第 k 层宽度为 2k-1，每一层均由 1 组成
  • 倒金字塔： 顶点在下，定义与正金字塔对称

⚠️ 高度至少为 2 才计入答案（单个点不算金字塔）。

二、问题建模（动态规划）

1. 状态定义

定义二维 DP 数组： \[ f(i,j) = \text{以 } (i,j) \text{ 为顶点的最大金字塔高度} \]

  • 若 grid[i][j] = 0，则 f(i,j) = 0
  • 若 grid[i][j] = 1，则至少有高度 1

2. 正金字塔的状态转移（向下扩展）

考虑 (i,j) 作为正金字塔顶点，其下一层需要：

  • (i+1, j-1)
  • (i+1, j)
  • (i+1, j+1)

三点均能支撑更低一层时，才能继续扩展。

状态转移方程

\[ f(i,j) = \begin{cases} 0, & grid(i,j)=0 \\ \min\bigl(f(i+1,j-1), f(i+1,j), f(i+1,j+1)\bigr) + 1, & grid(i,j)=1 \end{cases} \]

贡献计数

  • 高度为 h 的顶点，能形成 h-1 个合法金字塔（高度 ≥ 2）

\[ \text{贡献} = f(i,j) - 1 \]

3. 倒金字塔的状态转移（向上扩展）

倒金字塔与正金字塔完全对称，只需反向扫描矩阵。

状态转移方程

\[ f(i,j) = \begin{cases} 0, & grid(i,j)=0 \\ \min\bigl(f(i-1,j-1), f(i-1,j), f(i-1,j+1)\bigr) + 1, & grid(i,j)=1 \end{cases} \]

同样累加 f(i,j) - 1。

三、算法流程

  1. 从下往上 DP，统计所有正金字塔
  2. 清空 DP 数组
  3. 从上往下 DP，统计所有倒金字塔
  4. 返回两部分贡献之和

四、时间与空间复杂度

  • 时间复杂度： \[ O(n \times m) \]

  • 空间复杂度：

    • 普通 DP：O(n × m)
    • 滚动数组优化后：O(m)

五、参考实现（二维 DP 版本）

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
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int countPyramids(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int f[maxn][maxn] = {};  // f[i][j] 表示以 (i,j) 为顶点的最大高度
        int ans = 0;

        // ---------- 正金字塔（自下向上） ----------
        for (int i = n; i >= 1; --i) {
            for (int j = 1; j <= m; ++j) {
                if (grid[i - 1][j - 1] == 0)
                    continue;
                f[i][j] = min(
                    f[i + 1][j - 1],
                    min(f[i + 1][j], f[i + 1][j + 1])
                ) + 1;
                ans += f[i][j] - 1;  // 只统计高度 ≥ 2
            }
        }

        // 清空 DP 数组
        memset(f, 0, sizeof(f));

        // ---------- 倒金字塔（自上向下） ----------
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (grid[i - 1][j - 1] == 0)
                    continue;
                f[i][j] = min(
                    f[i - 1][j - 1],
                    min(f[i - 1][j], f[i - 1][j + 1])
                ) + 1;
                ans += f[i][j] - 1;
            }
        }

        return ans;
    }
};

六、滚动数组优化版本（空间压缩）

在状态转移中，f(i,j) 只依赖上一行，因此可将二维数组压缩为两行。

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
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int countPyramids(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int f[2][maxn] = {};  // 滚动数组
        int ans = 0;

        // ---------- 正金字塔 ----------
        for (int i = n; i >= 1; --i) {
            for (int j = 1; j <= m; ++j) {
                if (grid[i - 1][j - 1] == 0) {
                    f[i & 1][j] = 0;
                    continue;
                }
                f[i & 1][j] = min(
                    f[(i + 1) & 1][j - 1],
                    min(f[(i + 1) & 1][j], f[(i + 1) & 1][j + 1])
                ) + 1;
                ans += f[i & 1][j] - 1;
            }
        }

        memset(f, 0, sizeof(f));

        // ---------- 倒金字塔 ----------
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (grid[i - 1][j - 1] == 0) {
                    f[i & 1][j] = 0;
                    continue;
                }
                f[i & 1][j] = min(
                    f[(i - 1) & 1][j - 1],
                    min(f[(i - 1) & 1][j], f[(i - 1) & 1][j + 1])
                ) + 1;
                ans += f[i & 1][j] - 1;
            }
        }

        return ans;
    }
};

七、总结

  • 本题本质是三向最小值 DP 的二维建模
  • 金字塔高度自然刻画了“可形成多少个子金字塔”
  • 正反各做一次即可覆盖全部情况
  • 滚动数组可将空间从 O(nm) 优化到 O(m)