No Caffeine, No Life

プログラミング(主にPython)

AOJ DPL_3_A:最大正方形(Largest Square) 動的計画法

問題:

最大正方形 | 動的計画法 | Aizu Online Judge

解説:

  • {\displaystyle dp[ i ] [ j ] }:位置{\displaystyle (i, j) }から見て、左上に向かってできる最大の正方形の数

このように設定したとき、{\displaystyle dp[ i ] [ j ] }は、左上( {\displaystyle dp[ i-1 ] [ j-1 ] } )、左( {\displaystyle dp[ i ] [ j-1 ] } )、上( {\displaystyle dp[ i-1 ] [ j ] } )から決定される。すなわち、左上、左、上の要素の最小値+1となる:

{\displaystyle dp[ i+1 ] [ j+1 ] = min( dp[ i ] [ j ] , dp[ i+1 ] [ j ], dp[ i ] [ j+1 ] ) + 1 }

解答例: