[PYTHON] I personally chewed the explanation article of the section DP (Dharma doll drop)

In the section DP commentary article ( reference ), there was a part that I could not understand personally , I will chew it personally and explain it. (There may be a mistake in understanding ...)

The following two points could not be understood

1. Why release on the right side? It is divided into 2.2 cases, but are there any other cases?

1. 1. Why release right side?

・ Because index starts from 0 ・ If 0 <= l, r <n, the following expressions may be used.

TLE with AOJ, but stick a sauce like that at the bottom.

dp [l] [r]: = Number of blocks that can be removed in the interval [l, r]

・ Because I want to make a recursive expression using the interval division point (mid in the above reference article) as it is. When the expression is closed on both sides (that is, the interval [l, r]), the division is as follows.

Divide the section into [l, mid], [mid + 1, r]

It is divided into 2.2 cases, but are there any other cases?

In the reference article, the cases were divided as follows.

1. A block of l and a block of r -1 can be paired

2. Divide the section into [l, mid), [mid, r)

In case 1, all the parts sandwiched between both ends disappear, and the remaining ends disappear. Like the chain of Puyo Puyo. Case 2 is a case where the maximum number of removals is obtained for each part by dividing it into two parts.

Is there any other case for my question? That is. I didn't understand the reason for MECE in 2 cases. For example, what about the case where the part sandwiched between both ends disappears leaving two, and the remaining two disappear together with both ends? (Case A) What about the case where the part sandwiched between both ends disappears leaving one, and the remaining one disappears with either of the ends? (Case B)

When I wrote it in the figure, I found that it was included in the second case. (I haven't been able to prove that it fits in two cases)

Case A ![1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/694198/0c34b48b-23f9-5f91-7f4d-215ca4211f4a.png)

ケースB![2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/694198/db829c87-6eeb-b861-8584-ec076353dd6c.png)

import sys

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

def rec(l,r):
    #If it has already been searched, its value is returned.
    if dp[l][r] >= 0:
        return dp[l][r]

    #0 because a single case cannot be dropped
    if l == r:
        dp[l][r] = 0
        return 0

    #In the case of continuous parts
    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 All the parts sandwiched between both ends disappear, and the remaining both ends disappear
    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 The part sandwiched between both ends does not disappear
        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()