最大正方形問題の動的計画法による解法と考え方

最大正方形問題の解法とその考え方について、まとめたいと思います。
AIZU ONLINE JUDGEの例題をあげます。

例題

一辺が 1 cm のタイルが、H × W 個並べられています。タイルは汚れているもの、綺麗なもののいずれかです。
綺麗なタイルのみを使ってできる正方形の面積の最大値を求めてください。

入力

H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W

１行目に２つの整数 H、W が空白区切りで与えられます。続くH 行でタイルを表す H × W 個の整数 ci,j が与えられます。
ci,j が 1 のとき汚れたタイル、0 のとき綺麗なタイルを表します。

出力

面積の最大値を１行に出力してください。

入力例

4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

出力例

4

動的計画法を使った解法

小さな部分の問題の解を記録しておく領域をdp[H][W]として定義します。
dp[i][j]にタイル(i,j)から左上に向かってできる最大の正方形の辺長さ(タイルの数)を記録していきます。

この時の短縮方法について、図を用いて考えます。

上図のようにすでに、dpに2,1,3の正方形が入っているとします。
図で示されているように、正方形は左上に向かってできています。 これらの記録を利用して、?の部分の正方形の辺の長さを求めてみます。

dp[i][j]の値はその左上、上、左の要素の中で最も小さい値に1を加えたものになります。
図では、現在の位置(i,j)の右下とした正方形の辺の長さは、最小値である上の値1 + 1より大きくすることはできないことを示しています。

次のように、各行を左から右へ見ていく処理を、上から下へ順番に行えば、
dp[i][j]を計算する際に、左上、上、左の要素はすでに計算済みなので、これらの解を有効に利用することができます。

疑似言語による動的計画法を使った最大正方形を求めるアルゴリズム

for i = 1 to H - 1
 for j = 1 to W - 1
  if G[i][j] dirty
   dp[i][j] = 0
  else
   // 左上,上,左の最小値の+1がdp[i][j]の正方形の最大面積となる
   dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j - 1])) + 1
   // 最大値を更新
   maxWidth = max(maxWidth,dp[i][j]

では、例題の解法をc++で書いてみます。

#include 
#include
using namespace std;

#define MAX 1400

int dp[MAX][MAX],G[MAX][MAX];

int getLargestSquare(int h,int w){
    int maxWidth = 0;
    for(int i = 0;i < h;++i){
        for(int j = 0;j < w;++j){
            // 1が汚れたタイルなので、面積は0に、0は綺麗なタイルなので、面積が1になる
            dp[i][j] = (G[i][j] + 1) % 2;
            // 面積が1の場合、最大面積を計算する処理がスルーされるので、面積を暫定でいれる
            maxWidth |= dp[i][j];
        }
    }

    for(int i = 1;i < h;++i){
        for(int j = 1;j < w;++j){
            // 汚れている状態
            if(G[i][j]){
                dp[i][j] = 0;
            }else{
                // 左上,上,左の最小値の+1がdp[i][j]の正方形の最大面積となる
                dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j - 1])) + 1;
                maxWidth = max(maxWidth,dp[i][j]);
            }
        }
    }
    return maxWidth * maxWidth;
}

int main(){
    int h,w;
    scanf("%d %d",&h,&w);
    
    for(int i = 0;i < h;++i){
        for(int j = 0;j < w;++j){
            // 地面の状態
            scanf("%d",&G[i][j]);
        }
    }
    
    printf("%d\n",getLargestSquare(h,w));
    return 0;
}

参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造