動的計画法で解く

縦Hマス横Wマスに分割された長方形の領域Aに、
空きのマスと空きでないマスがある。
n個の長方形anに、縦Hnマス、横Wnマスの任意の大きさが与えられたとき、
各長方形を空きのマスに配置できる場所は
それぞれいくつあるかを求めるプログラムを書け。

A:       W
  □□□■□
  □□□□□
H □■□□■
  □□□□□
  □□■□□
□:空きのマス
■:空きでないマス

という問題と動的計画法を用いた模範解答のプログラムがWeb上で転がってたので、
そこからアルゴリズムを考えてみた。
飽くまで他人のプログラムを基に考えた、
「こういうアルゴリズムなんじゃないかなぁ」というものなので
ご容赦を。

まず上述のような領域の空き情報を配列a[H][W]に持っていたとする。

a	[][0]	[][1]	[][2]	[][3]	[][4]
[0][]	空き	空き	空き		空き
[1][]	空き	空き	空き	空き	空き
[2][]	空き		空き	空き
[3][]	空き	空き	空き	空き	空き
[4][]	空き	空き		空き	空き

動的計画法の計算に使う整数型の二次元配列dp[H][W+1]を宣言し、
整数型で表せる最大の数(めんどくさいのでここではIntMaxで表す)で初期化する。
(H,Wは領域Aの縦,横の大きさ ここではW=H=5)
dp[*][W] は0で初期化する。

dp	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[1][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[2][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[3][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[4][]	IntMax	IntMax	IntMax	IntMax	IntMax	0

大きさ別に何箇所配置できるかを格納する配列answer[H+1][W+1]。
0で初期化する。

ここから配置できる数を計算する過程に入ります。

まずa[0][]から順に、H1,W1〜W(=5)の小領域がいくつ配置出来るかを求めます。

1. a[0][j]が空きでなければdp[0][i]=0、空きならば、
   1. j==0 のとき dp[0][j]==0ならばdp[0][j]=0, dp[0][j]!=0ならば1
   2. j!=0 のとき dp[0][j]=min( dp[0][j-1]+1, dp[0][j])

a[0]に対してこの処理を行うとdp[]は

dp	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	1	2	3	0	1	0
[1][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[2][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[3][]	IntMax	IntMax	IntMax	IntMax	IntMax	0
[4][]	IntMax	IntMax	IntMax	IntMax	IntMax	0

こうなる。
するとdp[0][j]は、
a[0][j]の位置に置ける縦1マスの小領域の横の大きさの最大値となる。
(dp[0][2]=3は、「a[0][2]には縦1マスなら横3マスまでの小領域が置ける」という意味)

dp[1]〜dp[4]も同様に処理を行うと

dp	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	1	2	3	0	1	0
[1][]	1	2	3	4	5	0
[2][]	1	0	1	2	0	0
[3][]	1	2	3	4	5	0
[4][]	1	2	0	1	2	0

ここまで終わったら、いよいよanswer[1][w]に、
縦1マス横wマスの領域がいくつ配置できるかを計算していきます。
これはdp[i][j]>=wとなっている要素を数えてanswer[1][w]に格納すればよろしい。

answer	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	0	0	0	0	0	0
[1][]	0	21	13	7	4	2
[2][]	0	0	0	0	0	0
[3][]	0	0	0	0	0	0
[4][]	0	0	0	0	0	0
[5][]	0	0	0	0	0	0

さて、これで縦1マスの領域が置ける数はわかりました。
次からは縦2マス以上の領域が置ける数を求めます。

まず縦2横wの領域は、縦1横wの領域の下(a[i][j]に対してa[i+1][j])に
更に空きがあればそこに置くことが出来る。
なので、

1. a[i+1][j]が空きでなければdp[i][j]=0、空きならば、
   1. j==0 のとき dp[i][j]==0ならばdp[i][j]=0, dp[i][j]!=0ならばdp[i][j]=1
   2. j!=0 のとき dp[i][j]=min( dp[i][i-1]+1, dp[i][j])

これをdp[0]〜dp[3]に対して処理すると(1つ下を参照するので最下段はやらない)

dp	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	1	2	3	0	1	0
[1][]	1	0	1	2	0	0
[2][]	1	0	1	2	0	0
[3][]	1	2	0	1	2	0
[4][]	1	2	0	1	2	0

これでdp[i][0-3]は、
a[i][0-3]の位置に置ける縦2マスの小領域の横の大きさの最大値となる。

で、縦1マスのときと同じようにanswer[2]を更新します。
(dp[4]はカウントの対象外)

answer	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	0	0	0	0	0	0
[1][]	0	21	13	7	4	2
[2][]	0	14	6	1	0	0
[3][]	0	0	0	0	0	0
[4][]	0	0	0	0	0	0
[5][]	0	0	0	0	0	0

縦3マスの領域についても同様に処理を行うと

answer	[][0]	[][1]	[][2]	[][3]	[][4]	[][5]
[0][]	0	0	0	0	0	0
[1][]	0	21	13	7	4	2
[2][]	0	14	6	1	0	0
[3][]	0	7	1	0	0	0
[4][]	0	4	0	0	0	0
[5][]	0	1	0	0	0	0

ここまですれば、縦h横wの大きさをanswer[h][w]で指定してやればポンと
答えが出てくるわけです。

他人が書いたプログラムとはいえよく出来てるなぁ。
うーん、このアルゴリズム考えた人頭いいなぁ。

そして疲れた。