すべて 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 個の正方形があります。
  • 辺 3 には 1 個の正方形があります。
  • 正方形の合計数 = 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) のすべての ^subsquare をループし、合計により配列全体が 1 になるかどうかを確認します。確認された場合は、答えに 1 を加えます。

解決策:

動的計画法 (DP) を使用して、行列内の各セルで終わるすべて 1 の正方部分行列の数を追跡できます。これを達成するためのアプローチは次のとおりです:

1. DP マトリックス定義:

   • DP 行列 dp を定義します。ここで、dp[i][j] は、セル (i, j) に右下隅を持つすべて 1 の最大正方部分行列のサイズを表します。

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. 各位置 (i, j) で終わる最大の正方部分行列のサイズを追跡するために、2D 配列 dp を初期化します。
2. 行列内の各セルについて:
   • セルに 1 がある場合、隣接するセルに基づいて dp[i][j] を計算し、その値を totalSquares に追加します。
3. 最後に、totalSquares には、すべて 1 であるすべての正方部分行列の数が含まれます。

この解決策は効率的であり、問​​題で指定された制約を満たしています。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がすべて 1 で正方部分行列を数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。