区間DP(だるま落とし）の説明記事を個人的に咀嚼してみた

10101 ワード
区間DP AOJ AtCoder Python アルゴリズム Python テキストリンク

区間DPの解説記事で(参考)、個人的に理解できない箇所があったので、個人的に咀嚼して説明してみる。
（理解に誤りがあるかもしれないが。。。）

理解できなかった箇所は以下の２点

１．なぜ右側解放？
２．２ケースに分けているが、他のケースは無いのか？

１．なぜ右側解放?

・ただ単にindexが0始まりだから
・0<=l,r<nの場合は以下の表現でも良さそう
　※AOJでTLEするけど、それっぽいソースを最下部に張り付けておく。

dp[l][r] := 区間[l , r]で取り除くことのできるブロックの数

・区間分割点（上記参考記事ではmid）をそのまま使って再帰表現をしたいから
　両側が閉じた表現にした場合（つまり区間[l , r]）、以下の分け方になる。

[l,mid] , [mid+1 , r]に区間を分ける

２．２ケースに分けているが、他のケースは無いのか？

参考記事では以下の様にケース分けをしていた。

1. lのブロックとr - 1のブロックが対になれる
2. [l,mid) , [mid , r)に区間を分ける

1.のケースは、両端に挟まれている箇所がすべて消えて、さらに残った両端が消えるケース。ぷよぷよの連鎖みたいに。
2.のケースは、２分割してそれぞれのパート毎に最大の除去数を求めるケース

自分の疑問は、他にケースは無いのか？ということ。２ケースでMECEとなる理由が分からなかった。
たとえば、両端に挟まれている箇所が2個を残し消えて、さらに残った2個が両端とともに消えるケースはどうなのか？(ケースA)
両端に挟まれている箇所が1個を残し消えて、さらに残った1個が両端のいずれかとともに消えるケースはどうなのか？(ケースB)

図に書いてみると、2のケースに含まれることがわかった。
（２ケースに収まるという証明ができたわけではない）

ケースA
 ケースB 
import sys

sys.setrecursionlimit(250000)
input = sys.stdin.readline
dp = []
w =[]

def rec(l,r):
    #既に探索済の場合はその値を返す
    if dp[l][r] >= 0:
        return dp[l][r]

    #単一ケースは落とせないので0
    if l == r:
        dp[l][r] = 0
        return 0

    #連続している箇所の場合
    if l + 1 == r:
        if abs(w[l] - w[r]) <= 1:
            dp[l][r] = 2
            return 2
        else:
            dp[l][r] = 0
            return 0

    res = 0

    #Case1 両端に挟まれている箇所がすべて消えて、さらに残った両端が消える
    if abs(w[l] - w[r]) <= 1 and rec(l+1, r-1) == (r - 1) - (l + 1) + 1:
        res =  (r - 1) - (l + 1) + 1 + 2
    else: #Case2 両端に挟まれている箇所が消えない
        for mid in range(l,r):
            res = max(res, rec(l,mid)+rec(mid+1,r))

    dp[l][r]=res
    return res
def main():
    global w
    global dp
    n_list=[]
    w_list=[]

    while True:
        n = int(input())
        if n == 0 :
            break
        w_tmp = list(map(int, input().split()))
        n_list.append(n)
        w_list.append(w_tmp)

    for i in range(len(n_list)):
        dp = [[-1] * n_list[i] for j in range(n_list[i])]
        w = w_list[i]
        print(rec(0,n_list[i]-1))
main()