計算全為 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中文網其他相關文章！