* pe linia i, @auxdp[j][k] = valoarea minima a lui dp[i][h] cu h intre j si k.@

Definitia ne ajuta mai putin sa intelegem functionalitatea acestei dinamici. Ce facem cu ea este ca atunci cand am calculat s(i,j,k) + mv(i-1,j,k) pentru o subsecventa (j,k) in loc sa facem un _for_ de la j la k, incarcam valoarea in @auxdp[j][k]@. Dupa ce am parcurs toate subsecventele, facem actualizari in auxdp in felul urmator:

Definitia ne ajuta mai putin sa intelegem functionalitatea acestei dinamici. Ce facem cu ea este ca atunci cand am calculat s(i,j,k) + mv(i-1,j,k) pentru o subsecventa (j,k) in loc sa facem un _for_ de la j la k, incarcam valoarea in @auxdp[j][k]@. Dupa ce am parcurs toate subsecventele, parcurgem din nou subsecventele de coloane, de data aceasta in ordinea inversa a lungimii si actualizam in felul urmator:

* auxdp[j+1][k] = max (auxdp[j+1][k], auxdp[j][k]) cu j < k
* auxdp[j][k-1] = max (auxdp[j][k-1], auxdp[j][k]) cu j < k

^ Observam ca aici subsecventele trebuie parcurse in ordinea inversa a lungimii. La final, valoarea lui dp[i][j] se va afla nicaieri altundeva decat in auxdp[j][j]. Ce am facut practic a fost sa acumulam actualizarile in aceasta dinamica iar apoi sa le "impingem spre interior" catre punctele singulare, acelea fiind singurele valori de care avem nevoie mai departe.

La final, valoarea lui dp[i][j] se va afla nicaieri altundeva decat in auxdp[j][j]. Ce am facut practic a fost sa acumulam actualizarile in aceasta dinamica auxiliara iar apoi sa le "impingem spre interior" catre punctele singulare, acelea fiind singurele valori de care avem nevoie mai departe.

Exista si alte moduri de a face reducerea la <tex>O(N*M^2^)</tex>. Unii dintre voi le-ati aplicat in timpul concursului. Va invitam sa va ganditi la ele.