アルゴリズム

アルゴリズムI 中野

Note 2 ＤＰ 2020.4.6作成

4.30update 5.7update 5.10update 5.13update 5.14update

5.21update 2021.4.16update 5.11

動的計画法、

ダイナミックプログラミング、DP

動的計画法も、分割統治法のように、関連した幾つかの部分問題を解 くことにより解く。

動的計画法は、全ての部分問題をちょうど一回解き、答えを表に格納 する。

こうして、同じ部分問題を繰り返し解くことがないようにする。

部分問題の解の間には、階層構造(もしくは木構造)があることが多い。

このとき、下位の部分問題の解から、上位の部分問題の解を順に (Bottom Upに)

求められることが多い。

ダイナミックプログラミングの例

フィボナッチ数列

0 1 1 2 3 5 8 13 21 34 55…

if i = 0

f(0) = 0 ilse if I = 1

f(1) = 1 else

f (i) = f(i-1)+f(i-2)

アルゴリズムの例（分割統治法）

フィボナッチ数列

0 1 1 2 3 5 8 13 21 34 55…

F ( i ) if i = 0

f(0) = 0 ilse if i = 1

f(1) = 1 else

f (i) = f(i-1)+f(i-2)

f(10)

f(9) f(8)

f(8) f(7) f(7) f(6) f(7) f(6) f(6) f(5) f(6) f(5) f(5) f(4)

………..

O(2

) 時間アルゴリズム n 10 20 30

2

10

10

10

ダイナミックプログラミングの例

フィボナッチ数列

0 1 1 2 3 5 8 13 21 34 55…

Table Tを用意 T[0] = 0

T[1] = 1

for i = 2 to n

T[i] = T[i-1] + T[i-2]

i番目のフィボナッチ数 を計算するのは

ちょうど1回

O(n) 時間アルゴリズム

動的計画法

動的計画法は、最適化問題を解くのに、よく使われる。

最適化問題とは、多くの可能な解の中から、最適(最大もしくは 最小)の解を求めるものである。(最適解は複数あるかもしれない ことに注意! 同点一位があるかもしれないから。)

動的計画法は、次の3ステップからなる。

1. 最適解の構造をみつける。

2. 再帰的に最適解の値を定義する。

3. Bottom Up に最適解を計算する

幾つかの行列の積

n個の行列A₁, A₂ ,..., A_nの内積A₁・A₂・...・A_nを求めたい。

ただし、各A_iはp_i-1行、 p_i列行列とする。

乗算の数をなるべく少なくするには、との順で内積を求めたらよいだろうか？

(行列の乗算には結合則が成り立つことに注意) 例1 A₁,A₂,A₃,A₄の内積を求める方法は

( A₁ (A₂ ( A₃・A₄)) ) ( A₁ ((A₂・A₃) A₄) ) ( (A₁・A₂) (A₃・A₄) ) ( (A₁ (A₂・A₃)) A₄ ) ( ((A₁・A₂) A₃) A₄ )

の5通りある。(5つの木に対応することに注意!)

行列の個数がn+1個のとき、Catalan数個 = _2nC_n/(n+1)個 (これは 非常に大きい。)

全通りチェックはだめ

A₁ A₂ A₃ A₄

幾つかの行列の積

例2

5行5列の行列A1, 5行10列の行列A2, 10行5列の行列A3を、

(A1・A2)・A3

と計算すると乗算は 5・5・10 + 10・5・5 回 = (500回) 必要。

A1・(A2・A3)

と計算すると乗算は 10・5・5 + 5・5・5 回 = (375回) 必要。

5列

5行

5行

10列 5行

=

第i行

第j列 第i, j要素

乗算は5•5•10回必要

A

A

A

A

A

A

A

お得！

幾つかの行列の積（動的計画法）

1. 最適解の構造をみつける

i≦jのとき、Ai^・Ai+1^・Ai+2^・…・Ajの内積を、乗算の個数最小で求める方法を考えよう。

もし、i = jならば、(対象の行列は1個)、必要な乗算の回数は 0個である。

また、i+1 = j ならば、(対象の行列は2個)、必要な乗算の個数は、決まっている。

そうでないときは、複数の計算方法がある。

Ai^・Ai+1^・Ai+2^・…・Ajの内積を、乗算の個数最小で求めるとき、

最後に求める内積が、( Ai^・Ai+1^・Ai+2^・…・Ak^{)・( A}k+1^・Ak+2^・Ai+2^・…・Aj^{)であったとしよう。}

このとき、前半の、(Ai^・A

i+1

i+2

k

(そうでなければ、この内積を、さらに少ない個数の乗算で求めることができることになり矛盾を生じるので。)

同様に、後半の、(Ak+1^・Ak+2^・Ai+2^・…・Aj)の内積の計算の順序は、この内積を、乗算の個数最小で求めるような順序のはず。

つまり、問題の最適解は、部分問題の最適解と関係がある。

あとは、最後に求める内積が、すなわちkがどこであるのかを、上手に決めることができればよい。

( k = i, i+1 ,i+2, ..., j-1のいずれかであるので、これらをすべてチェックして最適なものを選べばよい。)

幾つかの行列の積（動的計画法）

2. 再帰的に最適解の値を定義する。

A

i

i+1

i+2

j

m[i,j]としよう。

最後に m[1,n]が解となる。

もし、i = j ならば 乗算は必要ないので、m[i,j] = 0 である。

もし、i < j ならば 下記のようになる。

最後に求める内積が、( Ai・Ai+1・Ai+2,..,Ak)・( Ak+1・Ak+2・Ai+2,..,Aj)であるとすると、

m[i,j] = m[i,k] + m[k+1,j] + pi-1 ^pk ^pj ^(各Ai^はpi-1^{行、 p}i^列行列)

k は i, i+1, i+2, ..., j-1 のいずれかであるので、これらを全て調べて、最も m[i,j]が小さくなるものを選べばよい。

つまり、

m[i,j] = mini≦k＜j { m[i,k] + m[k+1,j] + pi-1 ^pk ^pj ^} となる。

幾つかの行列の積（動的計画法）

3. Bottom Up に最適解を計算する。

Matrix-Chain-Order(P) {P は、p₀,p₁,...,p_nを格納する配列}

for i = 1 to n {行列の個数1個のとき}

m[i,i] = 0

for l = 2 to n { エル"l" は部分問題の行列の個数 } for i = 1 to n-l+1

j = i+l-1 m[i,j] = ∞

fork = i to j-1 { 最後の計算する内積の位置kを求める } q = m[i,k] + m[k+1,j] + p_i-1 p_k p_j}

if q < m[i,j] then {もっと乗算の少ない計算順序あれば更新}

m[i,j] = q

s[i,j] = k {計算の順序を格納}

return (配列) m および s

end

O(n

)時間アルゴリズム

幾つかの行列の積（具体例）

A

30行35列 A

35行15列 A

15行 5列

A

5行10列

A

10行20列 A

20行25列

i j

1

2

3

4

5

6 1

2

3

4

5

6

m[i,j]

幾つかの行列の積（具体例）

A

30行35列 A

35行15列 A

15行 5列

A

5行10列

A

10行20列 A

20行25列

i j

1

2

3

4

5

6 1

2

3

4

5

6

m[i,j]

0 0 0 0 0 0 l = 1

幾つかの行列の積（具体例）

A₁ 30行35列 A₂ 35行15列 A₃ 15行 5列 A₄ 5行10列 A₅ 10行20列 A₆ 20行25列

i j

1

2

3

4

5

6 1

2

3

4

5

6

m[i,j]

0 0 0 0 0 0

m[2,5]は

m[2,2]+m[3,5]+35・15・20=13000 m[2,3]+m[4,5]+35・ 5・20 = 7125 m[2,4]+m[5,5]+35・10・20 =11375

2625

4375 2500

1000

ナップサック問題(Knapsack problem)

1番からn番までの n個の物がある。

1≦i≦nなる各iについて、i番の物の重さはw

kgであり、

値段はv

万円である。

ナップサックを用いて、合計 W kg までの物を運べるとする。

このとき、値段が最大となるような物の組み合わせを選びたい。

最大の値段はいくらか？

問題の具体例

w

=1, w

=2, w

=5, w

=6, w

=7 (単位 kg) v

=1, v

=6, v

=18, v

=22, v

=28 (単位 万円)

W kgまで運べる

ナップサック問題(Knapsack problem)

1番からn番までの n個の物がある。

1≦i≦nなる各iについて、i番の物の重さはw

kgであり、

値段はv

万円である。

ナップサックを用いて、合計 W kg までの物を運べるとする。

このとき、値段が最大となるような物の組み合わせを選びたい。

最大の値段はいくらか？

選び方は 2

通り => 膨大な計算が必要！

W kgまで運べる

n 10 20 30 2ⁿ 10³ 10⁶ 10⁹

ナップサック問題(Knapsack problem)

部分問題P

を次のように定義する。

第i番目の物までは自由に選ぶことができ、第i+1番目以降の物は選べない。

ナップサックは、j kg まで運べる。

部分問題 P

の解をV(i,j)とする。

このとき、V(i,j)=max( V(i-1,j), V(i-1, j-w

) + v

)の関係がある。

(ただし、jが0か負のとき、もしくは、、iがゼロのとき、

V(i,j)はゼロとする。)

理由: 部分問題 P

の解は、

場合1: 部分問題 P

の解V(i-1,j)と同じ、(すなわち、i番目の物は選ばない)

場合2: 部分問題 P

の解V(i-1,j-w

)に、i番目の物を加えたもの(i番目の物は選ぶ)

のいずれかである。

V(i,j)=max( V(i-1,j), V(i-1, j-w _i )+v _i )

0 1 2 3 4 5 6 7 8 9 10 11

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

5番目まで選択可能

j

i

ここ が解 w₁=1, w₂=2, w₃=5, w₄=6, w₅=7 (単位 kg) v₁=1, v₂=6, v₃=18, v₄=22, v₅=28 (単位 万円)

O(Wn)時間アルゴリズム

V(i,j)=max( V(i-1,j), V(i-1, j-w _i )+v _i )

0 1 2 3 4 5 6 7 8 9 10 11

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

5番目まで選択可能

j

i

ここ が解

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0

w₁=1, w₂=2, w₃=5, w₄=6, w₅=7 (単位 kg) v₁=1, v₂=6, v₃=18, v₄=22, v₅=28 (単位 万円)

V(i,j)=max( V(i-1,j), V(i-1, j-w _i )+v _i )

0 1 2 3 4 5 6 7 8 9 10 11

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

5番目まで選択可能

j

i

ここ が解

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 6 7 7 7 7 7 7 7 7 7 1 6 7 7 18 19 24 25 25 25 25 1 6 7 7 18 22 24 28 29 29 40 1 6 7 7 18 22 28 29 34 35 40

w₁=1, w₂=2, w₃=5, w₄=6, w₅=7 (単位 kg) v₁=1, v₂=6, v₃=18, v₄=22, v₅=28 (単位 万円)

V(i,j)=max( V(i-1,j), V(i-1, j-w _i )+v _i )

0 1 2 3 4 5 6 7 8 9 10 11

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

5番目まで選択可能

j

i

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 6 7 7 7 7 7 7 7 7 7 1 6 7 7 18 19 24 25 25 25 25 1 6 7 7 18 22 24 28 29 29 40 1 6 7 7 18 22 28 29 34 35 40

w₁=1, w₂=2, w₃

=5, w

=6, w

=18, v

=22, v

最長共通部分文字列 (Longest Common Subsequence)

DNAは4種類(ACGT)の塩基の列と見なせる。すわわち、4種類の文字の列とみなせる。

2つのDNAの類似性を、与えられた基準に従って(高速に)求めたい。

2つの文字列S1とS2の類似性の基準には様々なものがある。

今回は、S1とS2中に共通に含まれる文字列S3によって定義する。

S3の各文字は、S1とS2中に(順序に従って)現れるとする。ただし、連続して現れなくてもよいとする。

このような文字列のうち最大のものを選び(これを最長共通部分文字列と呼ぶ)、

この長さが長いほど、S1とS2は似ているとしよう。

最長共通部分文字列を求めるには、どうしたらよいだろうか？

例 S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA のとき

S3 = GTCGTCGGAAGCCGGCCGAA が最長である。

最長共通部分文字列

問題

文字列 X = ( x

,x

,...,x

)と

Y = ( y

,y

,...,y

)が、与えられたとき、

XとYの最長共通部分文字列を求めよ。

素朴な方法

X の部分文字列を全て生成し( 2

個ある)、

これらが Y の部分文字列であるかどうかを調べればよい。

しかし、膨大な時間がかかる。

動的計画法で解こう!

最長共通部分文字列

1. 最適解の構造をみつける。

X = ( x₁,x₂,...,x_m) と Y = ( y₁,y₂,...,y_n)との最長共通部分文字列は Z = ( z₁,z₂,...,z_k)であったとする。

このとき、次の3つの場合がある。

場合1: x_m = y_n のとき。 このとき、z_k = x_m = y_nである。

z₁,z₂,...,z_kー1は、

x₁,x₂,...,x_m-1とy₁,y₂,...,y_n-1との最長共通部分文字列である。

(つまり、少し小さい部分問題の解を求めれば、問題の解がわかる!)

場合2: x_m ≠ y_n かつ z_k ≠ x_m のとき。 このとき、Xの最後の文字x_mは無用である。

z₁,z₂,...,z_kは、

x₁,x₂,...,x_m-1とy₁,y₂,...,y_nとの最長共通部分文字列である。

場合3: x_m ≠ y_n かつ z_k ≠ y_n のとき。 このとき、Yの最後の文字y_nは無用である。

z₁,z₂,...,z_kは、

x₁,x₂,...,x_mとy₁,y₂,...,y_n-1との最長共通部分文字列である。

X

X

X Y

Y

Y

最長共通部分文字列

2. 再帰的に最適解の値を定義する。

もし、元の問題よりもすこし短い下記の3種類の問題の解がわかれば、元の問題の解も (次に説明するようにして）計算できる。

問題1: x_1,x₂,...,x_m-1とy₁,y₂,...,y_n-1との最長共通部分文字列。

問題2: x₁,x₂,...,x_m-1とy₁,y₂,...,y_nとの最長共通部分文字列。

問題3: x₁,x₂,...,x_mとy₁,y₂,...,y_n-1との最長共通部分文字列。

もし、x_m = y_nならば、元の問題の解は、問題1の解の最後に、1文字 x_mを追加したものである。

もし、x_m ≠ y_nならば、元の問題の解は、問題2の解と3の解のうち、長い方である。

(つまり、x_mを使用しないか、y_nを使用しないか、両方使用しないか、のいずれかである。)

2つの文字列x₁,x₂,...,xi^{とy1,y2,...,y}jとの最長共通部分文字列の長さを c[i,j] と書こう。

もし、i、もしくは、jが0ならば、c[i,j] は0である。

そうでないときは、次の式が得られる。

xi ^{= y}j ならば、c[i,j] = c[i-1,j-1] +1 である。

xi ^{≠ y}j ならば、c[i,j] = max { c[i,j-1], c[i-1,j] } である。

X

X

X Y

Y

Y

最長共通部分文字列

3. Bottom Up に最適解を計算する。

LCS-Length(X,Y) {X,Yは2つの文字列を格納する配列}

{X はm文字であり、 Y はn文字であるとする} {c は c[i,j]を格納する2次元配列}

for i = 1 to m c[i,0] = 0 {Yが0文字のとき}

for j = 1 to n c[0,j] = 0 {Xが0文字のとき}

for i = 1 to m

for j = 1 to n if x

= y

then

c[i,j] = c[i-1,j-1] +1

else if c[i-1,j] ≧ c[i,j-1] then c[i,j] = c[i-1,j]

else c[i,j] = c[i,j-1]

return c

最長共通部分文字列 (具体例）

X = abcbdab Y = bdcaba

0 1 2 3 4 5 6 b d c a b a 0

1 2 3 4 5 6 7 X

Y

ここ が解 a

b c b d a b

最長共通部分文字列 (具体例）

X = abcbdab Y = bdcaba

0 1 2 3 4 5 6 b d c a b a 0

1 2 3 4 5 6 7 X

Y

ここ が解 a

b c b d a b

0 0 0 0 0 0 0 0

0 0 0 0 0 0

最長共通部分文字列 (具体例）

X = abcbdab Y = bdcaba

0 1 2 3 4 5 6 b d c a b a 0

1 2 3 4 5 6 7 X

Y

ここ が解 a

b c b d a b

0 0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 2 2 1 1 2 2 2 2 1 1 2 2 3 3 1 2 2 2 3 3 1 2 2 3 3 4 1 2 2 3 4 4

最長共通部分文字列 (具体例）

X = abcbdab Y = bdcaba

Z = bcba

0 1 2 3 4 5 6

b

c

b a

1 2 3 4 5 6 7 X

Y

ここ が解 a

b c b

a

0 0 0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 2 2 1 1 2 2 2 2 1 1 2 2 3 3 1 2 2 2 3 3 1 2 2 3 3 4 1 2 2 3 4 4

理解認識クイズ

(1) 4つの配列A1,A2,A3,A4がある。それぞれ5行10列、10行5列、

5行2列、2行5列である。このとき乗算をなるべく少なく使って 内積A1・A2・A3・A4を計算したい。どのような順序で計算をす ればよいか？またそのときの乗算の回数は何回か？

A1 A2 A3 A4

5行10列

10行5列

5行2列

2行5列

理解認識クイズ

復習 乗算の回数は？

１ ２ ３ ２ ４ ６

（ ) (

) ⁼

( )

2行3列

2行1列

乗算は 3 * 2 * 1 回必要

a行b列

乗算は

b c a回必要

5列

5行

5行

10列 5行

=

第i行

第j列 第i, j要素

乗算は5•5•10回必要

i j

1

2

3 1 4

2

3

4

m[i,j]

A1 A2 A3 A4

5行10列

10行5列

5行2列

2行5列

0 0 0 0

A1 A2 は 乗算 10•5•5 = 250回 A2 A3 は 乗算 5•10•2 = 100回 A3 A4 は 乗算 2•5•5 = 50回

250 100 50

i j

1

2

3 1 4

2

3

4

m[i,j]

A1 A2 A3 A4

5行10列

10行5列

5行2列

2行5列

0 0 0 0

A1 A2 A3 は 乗算?回 (A1 A2)A3なら乗算

250+0+5•5•2 = 300回 A1( A2 A3)なら乗算

0 + 100+ 10•5•2=200回<=こちら

250 100 50

200

i j

1

2

3 1 4

2

3

4

m[i,j]

A1 A2 A3 A4

5行10列

10行5列

5行2列

2行5列

0 0 0 0

A2 A3 A4 は 乗算?回 (A2 A3)A4なら乗算

100+0+2•10•5 = 200回<=こちら A2( A3 A4)なら乗算

0 + 50+ 5•10•5=300回

250 100 50

200 200

i j

1

2

3 1 4

2

3

4

m[i,j]

A1 A2 A3 A4

5行10列

10行5列

5行2列

2行5列

0 0 0 0

A1 A2 A3 A4 は 乗算?回 (A1 A2 A3)A4なら乗算

200+0+2•5•5 = 250回<=こちら (A1 A2)(A3 A4)なら乗算

250 + 50+ 5•5•5=425回 A1 (A2 A3 A4)なら乗算

0 + 200 + 10•5•5= 450

250 100 50 200 200

250

(A1 (A2 A3)) A4の順序がお得

理解認識クイズ

(2)

1番から4番まで4つの物がある。

1番の物は、重さ2 kg, 値段 3万円である。

2番の物は、重さ3 kg, 値段 4万円である。

3番の物は、重さ2 kg, 値段 2万円である。

4番の物は、重さ3 kg, 値段 6万円である。

この中から、合計9 kg まで、物をいくつか選びたい。

選んだ物の値段の合計が最大になるようにするには、どのように選べばよ いか？

この問題を解くアルゴリズムを説明せよ。

アルゴリズムが作成する表を書け。

そのアルゴリズムの計算時間を説明せよ。

1番から4番まで4つの物がある。

1番の物は、重さ2 kg, 値段 3万円である。

2番の物は、重さ3 kg, 値段 4万円である。

3番の物は、重さ2 kg, 値段 2万円である。

4番の物は、重さ3 kg, 値段 6万円である。

この中から、合計9 kg まで、物をいくつか選びたい。

0 1 2 3 4 5 6 7 8 9

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

0 0 0 0 0 0 0 0 0 0 0

0 0 0

0

1番から4番まで4つの物がある。

1番の物は、重さ2 kg, 値段 3万円である。

2番の物は、重さ3 kg, 値段 4万円である。

3番の物は、重さ2 kg, 値段 2万円である。

4番の物は、重さ3 kg, 値段 6万円である。

この中から、合計9 kg まで、物をいくつか選びたい。

0 1 2 3 4 5 6 7 8 9

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

0 0 0 0 0 0 0 0 0 0 0

0 0 0

0 3 3 3 3 3 3 3 3

0 3 4 4 7 7 7 7 7

0 3 4 5 7 7 9 9 9

0 3 6 6 9 10 11 13 13

1番から4番まで4つの物がある。

1番の物は、重さ2 kg, 値段 3万円である。

2番の物は、重さ3 kg, 値段 4万円である。

3番の物は、重さ2 kg, 値段 2万円である。

4番の物は、重さ3 kg, 値段 6万円である。

この中から、合計9 kg まで、物をいくつか選びたい。

0 1 2 3 4 5 6 7 8 9

0番目まで選択可能

1番目まで選択可能 2番目まで選択可能

3番目まで選択可能

4番目まで選択可能

0 0 0 0 0 0 0 0 0 0 0

0 0 0

0 3 3 3 3 3 3 3 3

0 3 4 4 7 7 7 7 7

0 3 4 5 7 7 9 9 9

0 3 6 6 9 10 11 13 13

理解認識クイズ

(3) プログラム Matrix-Chain-Order(P)中で、配列s の役割は何か？

(4) ナップサック問題を解く動的計画法アルゴリズムにおいて、w

はソート しておく必要があるだろうか？

(5) ナップサック問題を解く動的計画法アルゴリズムにおいて、選択した物 の組み合わせを求めるには、どうしたらよいであろうか？

(6) 2つの文字列 BCACBCC と ABCBCC の最長共通部分文字列を上の

アルゴリズムを使用して求めよ。

(6) 2つの文字列 BCACBCC と ABCBCC の最長共通部分文字列を 上のアルゴリズムを使用して求めよ。

X = BCACBCC Y = ABCBCC

0 1 2 3 4 5 6 A B C B C C 0

1 2 3 4 5 6 7 X

Y

ここ が解 B

C A C B C C

(6) 2つの文字列 BCACBCC と ABCBCC の最長共通部分文字列を 上のアルゴリズムを使用して求めよ。

X = BCACBCC Y = ABCBCC

0 1 2 3 4 5 6 A B C B C C 0

1 2 3 4 5 6 7 X

Y

ここ が解 B

C A C B C C

0 0 0 0 0 0

0 0 0 0 0 0 0

0 1 1 1 1 1

0 1 2 2 2 2

1 1 2 2 2 2

1 1 2 3 3

1 2 2 3 3 3 1 2 3 3 4 4 1 2 3 3 4 5

(6) 2つの文字列 BCACBCC と ABCBCC の最長共通部分文字列を 上のアルゴリズムを使用して求めよ。

X = BCACBCC Y = ABCBCC

0 1 2 3 4 5 6 A

B C B C C

1 2 3 4 5 6 7 X

Y

ここ が解

B

C A

C B C C

0 0 0 0 0 0

0 0 0 0 0 0 0

0 1 1 1 1 1

0 1 2 2 2 2

1 1 2 2 2 2

1 1 2 3 3

1 2 2 3 3 3 1 2 3 3 4 4 1 2 3 3 4 5