What is the core idea behind Count Fertile Pyramids in a Land?

The core idea is state transition dynamic programming on the matrix. For each fertile cell, you compute the tallest pyramid it can be the apex of by looking at three supporting cells in the adjacent row, then add the number of valid heights above one.

Why does the transition use the minimum of three neighboring states?

A pyramid can only grow if its next level is fully supported on the left, center, and right. The smallest of those three heights limits how many complete wider layers can exist below the current apex, so the minimum exactly captures the failure point.

How do you count inverse pyramids in this problem?

Use the same DP idea in the opposite direction. You can scan from top to bottom with a mirrored transition, or reverse the grid vertically and run the upright pyramid routine again.

Why is brute force too slow for problem 2088?

If you try every fertile cell as a center and expand height by height while checking row widths, you repeat work heavily across overlapping pyramids. With up to 10^5 cells, that repeated validation is much slower than one DP pass per orientation.

Can this dynamic programming pattern be optimized for space?

Yes. Each pass depends only on one neighboring row, so you do not need to keep the full m by n table if you only want the count. Rolling arrays can reduce the auxiliary space to O(n), though the indexing becomes easier to get wrong.

#2088

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

有一个矩形网格状的农场，划分为 m 行 n 列的单元格。每个格子要么是肥沃的（用 1 表示），要么是贫瘠的（用 0 表示）。网格图以外的所有与格子都视为贫瘠的。农场中的金字塔区域定义如下：区域内格子数目大于 1 且所有格子都是肥沃的。金字塔顶端是这个金字塔最上方的…

数组动态规划矩阵

题目描述

有一个 矩形网格 状的农场，划分为 m 行 n 列的单元格。每个格子要么是 肥沃的 （用 1 表示），要么是贫瘠的（用 0 表示）。网格图以外的所有与格子都视为贫瘠的。

农场中的 金字塔 区域定义如下：

区域内格子数目大于 1 且所有格子都是 肥沃的 。
金字塔顶端是这个金字塔 最上方 的格子。金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r <= i <= r + h - 1 且 c - (i - r) <= j <= c + (i - r) 。

一个 倒金字塔 类似定义如下：

区域内格子数目大于 1 且所有格子都是 肥沃的 。
倒金字塔的顶端是这个倒金字塔 最下方 的格子。倒金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r - h + 1 <= i <= r 且 c - (r - i) <= j <= c + (r - i) 。

下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。

给你一个下标从 0 开始且大小为 m x n 的二进制矩阵 grid ，它表示农场，请你返回 grid 中金字塔和倒金字塔的 总数目 。

示例 1：

输入：grid = [[0,1,1,0],[1,1,1,1]]
输出：2
解释：
2 个可能的金字塔区域分别如上图蓝色和红色区域所示。
这个网格图中没有倒金字塔区域。
所以金字塔区域总数为 2 + 0 = 2 。

示例 2：

输入：grid = [[1,1,1],[1,1,1]]
输出：2
解释：
金字塔区域如上图蓝色区域所示，倒金字塔如上图红色区域所示。
所以金字塔区域总数目为 1 + 1 = 2 。

示例 3：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：0
解释：
网格图中没有任何金字塔或倒金字塔区域。

示例 4：

输入：grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
输出：13
解释：
有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。
有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。
所以金字塔区域总数目为 7 + 6 = 13.

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
grid[i][j] 要么是 0 ，要么是 1 。

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示以 $(i, j)$ 为顶点的金字塔的最大高度，那么有如下状态转移方程：

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

因此，我们可以从下往上、从左往右遍历网格，计算出所有的 $f[i][j]$ ，并累加所有的 $f[i][j]$ 即可得到正金字塔的个数。

接下来，我们考虑倒金字塔的个数。与金字塔类似，我们定义 $g[i][j]$ 表示以 $(i, j)$ 为顶点的倒金字塔的最大高度，那么有如下状态转移方程：

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

因此，我们可以从上往下、从左往右遍历网格，计算出所有的 $g[i][j]$ ，并累加所有的 $g[i][j]$ 即可得到倒金字塔的个数。

最后，正金字塔的个数加上倒金字塔的个数即为答案。实际代码中，我们可以只用一个二维数组 $f[i][j]$ 即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为网格的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[0] * n for _ in range(m)]
        ans = 0
        for i in range(m - 1, -1, -1):
            for j in range(n):
                if grid[i][j] == 0:
                    f[i][j] = -1
                elif not (i == m - 1 or j == 0 or j == n - 1):
                    f[i][j] = min(f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]) + 1
                    ans += f[i][j]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    f[i][j] = -1
                elif i == 0 or j == 0 or j == n - 1:
                    f[i][j] = 0
                else:
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + 1
                    ans += f[i][j]
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to stop brute forcing heights and define a DP state that stores the tallest pyramid centered at each cell.
question_mark
They are checking whether you notice that every apex contributes multiple pyramids when its maximum height is greater than 2.
question_mark
They expect you to exploit symmetry for inverse pyramids instead of writing a slow second validation routine.

warning

常见陷阱

外企场景

error
Counting height 1 cells as pyramids, which inflates the result immediately on dense grids.
error
Using width validation for every candidate height, which turns this matrix problem into a slow repeated scan.
error
Forgetting boundary behavior in the transition, especially that edge cells cannot grow because one side of the next row is missing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the number of upright pyramids only, which removes the second pass but keeps the same DP transition.
arrow_right_alt
Return the maximum pyramid height anywhere in the grid instead of the total count, which uses the same state without summation.
arrow_right_alt
Allow queries that flip cells between fertile and barren, which breaks the static DP and would need a very different update strategy.

help

常见问题

外企场景

继续练习

#1981 最小化目标值与所选元素的差 #1937 扣分后的最大得分 #2267 检查是否有合法括号字符串路径