计算全为 1 的方形子矩阵

1277。计算全为 1 的方形子矩阵

难度：中等

主题：数组、动态规划、矩阵

给定一个由 1 和 0 组成的 m * n 矩阵，返回 有多少个 方 子矩阵全部为 1。

示例1：

• 输入： 矩阵 = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
• 输出： 15
• 说明：
  • 边长 1 有 10 个正方形。
  • 边长 2 有 4 个正方形。
  • 有 1 个边长为 3 的正方形。
  • 方格总数 = 10 4 1 = 15.

示例2：

• 输入： 矩阵 = [[1,0,1], [1,1,0], [1,1,0]]
• 输出： 7
• 说明：
  • 边长为 1 的正方形有 6 个。
  • 边长 2 有 1 个正方形。
  • 方格总数 = 6 1 = 7。

约束：

• 1
• 1
• 0

提示：

1. 创建一个加法表，计算上角位于 (0,0) 的 子矩阵 的元素总和。
2. 在 O(n3) 中循环所有 ^子方，并检查总和是否使整个数组为 1，如果检查结果为 1，则在答案中加 1。

解决方案：

我们可以使用动态规划（DP）来跟踪方子矩阵的数量，其中所有子矩阵都可以在矩阵中的每个单元格结束。以下是实现这一目标的方法：

1. DP 矩阵定义:

   • 定义一个 DP 矩阵 dp，其中 dp[i][j] 表示右下角位于单元格 (i, j) 的所有子矩阵的最大方形子矩阵的大小。

2. 过渡公式:

   • 对于矩阵中的每个单元格 (i, j)：

     • 如果matrix[i][j]为1，则dp[i][j]的值取决于从(i-1,j)延伸形成的平方的最小值，(i,j -1) 和 (i-1, j-1)。过渡公式为：

     dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
     

  - If `matrix[i][j]` is 0, `dp[i][j]` will be 0 because a square of ones cannot end at a cell with a zero.

1. 计算所有方块:

   • 将所有 (i, j) 的 dp[i][j] 值累加，得到所有大小的方格总数。

2. 时间复杂度:

   • 该解决方案适用于 O(m X n)，其中 m 和 n 是矩阵的维度。

让我们用 PHP 实现这个解决方案：1277。计算全为 1 的方形子矩阵

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

解释：

1. 我们初始化一个二维数组 dp 来跟踪在每个位置 (i, j) 结束的最大方形子矩阵的大小。
2. 对于矩阵中的每个单元格：
   • 如果单元格的值为 1，我们会根据相邻单元格计算 dp[i][j]，并将其值添加到totalSquares 中。
3. 最后，totalSquares 包含所有全为 1 的方形子矩阵的计数。

这个解决方案是高效的并且满足问题中提供的约束。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是计算全为 1 的方形子矩阵的详细内容。更多信息请关注PHP中文网其他相关文章！