【C++动态规划】2088. 统计农场中肥沃金字塔的数目|2104
本文涉及知识点
LeetCode2088. 统计农场中肥沃金字塔的数目
有一个 矩形网格 状的农场，划分为 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 <= 105
grid[i][j] 要么是 0 ，要么是 1 。
动态规划
先求正金字塔数量，然后第i行和R-1-i行互换，i $[0,R/2-1]，再求正金字塔数量。
#动态规划的装表示
H金字 = min((C+1)/2,R)
动态规划的状态表示
dp[h][r][c]表示 以(r,c)为顶，高度为h的正金子塔是否存在。 空间复杂度：O(RCH)
动态规划的填表顺序
h = 2 To H r = 0 To r+h <= R c to 0 To c+h <= C
dp[h][r][c] = grid[r][c]&&grid[r+1][c]&&[h-1]dp[r+1][c-1]&&dp[h-1][r+1][c+1]
单个状态的时间复杂度：O(1)，总时间复杂度：O(RCH)
动态规划的初始化
dp[1] = grid[r][c]
可用滚动向量
动态规划的返回值
dp[2…H]之和。
代码
核心代码
classSolution{public:intcountPyramids(vector<vector<int>>& grid){constint R = grid.size();auto rev = grid;for(int r =0; r < R /2; r++){ rev[r].swap(rev[R -1- r]);}returnDo(grid)+Do(rev);}intDo(const vector<vector<int>>& grid){constint R = grid.size();constint C = grid[0].size();constint H =min(R,(C +1)/2);auto pre = grid;int ans =0;for(int h =2; h <= H; h++){ vector<vector<int>>cur(R,vector<int>(C));for(int r =0; r+ h <= R ;r++)for(int c = h-1; c + h <= C; c++){ cur[r][c]= pre[r][c]&& pre[r +1][c -1]&& pre[r +1][c]&& pre[r +1][c +1]; ans += cur[r][c];} pre.swap(cur);}return ans;}};单元测试
vector<vector<int>> grid;TEST_METHOD(TestMethod11){ grid ={{0,1,1,0},{1,1,1,1}};auto res =Solution().countPyramids(grid);AssertEx(2, res);}TEST_METHOD(TestMethod12){ grid ={{1,1,1},{1,1,1}};auto res =Solution().countPyramids(grid);AssertEx(2, res);}TEST_METHOD(TestMethod13){ grid ={{1,0,1},{0,0,0},{1,0,1}};auto res =Solution().countPyramids(grid);AssertEx(0, res);}TEST_METHOD(TestMethod14){ grid ={{1,1,1,1,0},{1,1,1,1,1},{1,1,1,1,1},{0,1,0,0,1}};auto res =Solution().countPyramids(grid);AssertEx(13, res);}TEST_METHOD(TestMethod15){ grid.assign(1000,vector<int>(100,1));auto res =Solution().countPyramids(grid);AssertEx(4816700, res);}优化
如果(r,c,h)是金子塔，则(r,c,h-1)也是金子塔。
动态规划的状态表示
dp[r][c]记录最大h。空间复杂度：O(mn)
动态规划的填表顺序
r = R-2 to 0 c = 1 to C-2
动态规划的转移方程
{ d p [ r ] [ c ] = 0 0 = = g r i d [ r ] [ c ] d p [ r ] [ c ] = 1 + m i n ( d p [ r + 1 ] [ c − 1 ] + d p [ r + 1 ] [ c ] + d p [ r + 1 ] [ c + 1 ] ) o t h e r \begin{cases} dp[r][c] = 0 && 0 == grid[r][c] \\ dp[r][c] = 1 +min(dp[r+1][c-1]+dp[r+1][c]+dp[r+1][c+1]) && other\\ \end{cases} {dp[r][c]=0dp[r][c]=1+min(dp[r+1][c−1]+dp[r+1][c]+dp[r+1][c+1])0==grid[r][c]other
空间复杂度：O(mn)
动态规划的初始值
dp = grid
动态规划的返回值
dp之和-gird之和
代码
classSolution{public:intcountPyramids(vector<vector<int>>& grid){constint R = grid.size();auto rev = grid;for(int r =0; r < R /2; r++){ rev[r].swap(rev[R -1- r]);}returnDo(grid)+Do(rev);}intDo(const vector<vector<int>>& grid){constint R = grid.size();constint C = grid[0].size();auto dp = grid;for(int r = R-2;r >=0; r--)for(int c =1; c < C -1; c++){if(0== grid[r][c]){continue;} dp[r][c]=1+*min_element(dp[r+1].begin()+ c -1, dp[r+1].begin()+ c +2);}int ans =0;for(constauto& v : dp){ ans +=accumulate(v.begin(), v.end(),0);}for(constauto& v : grid){ ans -=accumulate(v.begin(), v.end(),0);}return ans;}};扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
