[PYTHON] J'ai personnellement mâché l'article d'explication de la section DP (Daruma drop)

Dans l'article de commentaire de la section DP ( référence ), il y avait une partie que je ne pouvais pas comprendre personnellement. J'essaierai de l'expliquer en le mâchant personnellement. (Il peut y avoir une erreur de compréhension ...)

Les deux points suivants n'ont pas pu être compris

1. Pourquoi sortir du bon côté? Il est divisé en 2,2 cas, mais y a-t-il d'autres cas?

1. 1. Pourquoi relâcher le côté droit?

・ Parce que l'index commence à 0 ・ Si 0 <= l, r <n, les expressions suivantes peuvent être utilisées.

TLE avec AOJ, mais collez une sauce comme ça au fond.

dp [l] [r]: = nombre de blocs pouvant être supprimés dans l'intervalle [l, r]

・ Parce que je veux utiliser le point de division de section (au milieu de l'article de référence ci-dessus) comme c'est le cas pour l'expression récursive. Lorsque l'expression est fermée des deux côtés (c'est-à-dire l'intervalle [l, r]), la division est la suivante.

Divise la section en [l, mid], [mid + 1, r]

Il est divisé en 2,2 cas, mais y a-t-il d'autres cas?

Dans l'article de référence, les affaires ont été réparties comme suit.

1. Un bloc de l et un bloc de r -1 peuvent être appariés

2. Divisez la section en [l, mid), [mid, r)

Dans le cas 1, toutes les pièces prises en sandwich entre les deux extrémités disparaissent et les extrémités restantes disparaissent. Comme une chaîne de puyopuyo. Le cas 2 est un cas où le nombre maximum d'enlèvements est calculé pour chaque pièce en le divisant en deux parties.

Y a-t-il un autre cas pour ma question? C'est. Je n'ai pas compris la raison de MECE dans 2 cas. Par exemple, qu'en est-il du cas où la partie prise en sandwich entre les deux extrémités disparaît en laissant deux, et les deux autres disparaissent avec les deux extrémités? (Cas A) Qu'en est-il du cas où la partie prise en sandwich entre les deux extrémités disparaît en laissant une, et la partie restante disparaît avec l'une des extrémités? (Cas B)

Quand je l'ai écrit dans la figure, j'ai trouvé qu'il était inclus dans le deuxième cas. (Je n'ai pas pu prouver que ça rentre dans deux cas)

Cas 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):
    #S'il a déjà été recherché, sa valeur est renvoyée.
    if dp[l][r] >= 0:
        return dp[l][r]

    #0 car un seul cas ne peut pas être abandonné
    if l == r:
        dp[l][r] = 0
        return 0

    #Dans le cas de pièces continues
    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

    #Cas 1 Toutes les pièces prises en sandwich entre les deux extrémités disparaissent et les deux extrémités restantes disparaissent
    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: #Cas 2 La partie prise en sandwich entre les deux extrémités ne disparaît pas
        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()