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
・ Because index starts from 0 ・ If 0 <= l, r <n, the following expressions may be used.
・ 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.
In the reference article, the cases were divided as follows.
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()