本文涉及知识点
C++动态规划
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]之和。
代码
核心代码
class Solution {
public:
int countPyramids(vector<vector<int>>& grid) {
const int R = grid.size();
auto rev = grid;
for (int r = 0; r < R / 2; r++) {
rev[r].swap(rev[R - 1 - r]);
}
return Do(grid) + Do(rev);
}
int Do(const vector<vector<int>>& grid) {
const int R = grid.size();
const int C = grid[0].size();
const int 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之和
代码
class Solution {
public:
int countPyramids(vector<vector<int>>& grid) {
const int R = grid.size();
auto rev = grid;
for (int r = 0; r < R / 2; r++) {
rev[r].swap(rev[R - 1 - r]);
}
return Do(grid) + Do(rev);
}
int Do(const vector<vector<int>>& grid) {
const int R = grid.size();
const int 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 (const auto& v : dp) {
ans += accumulate(v.begin(), v.end(),0);
}
for (const auto& v : grid) {
ans -= accumulate(v.begin(), v.end(), 0);
}
return ans;
}
};
