Redu

Problema se poate rezolva cu programare dinamica. Fie din[i][j] = costul minim cu care pot sa reduc secventa dintre pozitiile i si j. Ca sa determinam din[i][j] putem sa ne gandim in urmatorul fel: primul caracter (cel de pe pozitia i) il putem reduce ultimul cu un alt caracter de pe o pozitie oarecare k din subsecventa, fara a afecta in nici un fel optimalitatea solutiei. Dar pentru aceasta trebuie mai intai sa reducem secventa (i + 1, k - 1) si secventa (k + 1, j) si apoi sa reducem cele doua caractere ramase. Vizual:

i ___S1___ k _____S2_____j

Pentru a reduce caracterul de pe pozitia i cu cel de pe pozitia k trebuie sa reducem S1, S2 (incluzand pozitia j) si apoi cele doua caractere ramase S[i], S[k].

Asadar pentru a gasi solutia optima trebuie doar sa incercam toate k-urile posibile si sa o alegem pe cea mai buna. Astfel recurenta dinamicii se contureaza in acest mod: din[i][j] = MIN ( din[i + 1][k - 1] + din[k + 1][j] + C[ S[i] ][ S[k] ]) pentru oricare k=i+1,j. Trebuie sa avem atentie la cateva cazuri particulare:

• din[i][j], unde j - i + 1 nu este par este INFINIT (nu se poate reduce o secventa de lungime impara)
• din[i][j], unde i > j este 0 (ajungem in aceste cazuri prin recurenta noastra, dar ele reprezinta siruri vide)
• din[i][j], unde i + 1 = j este C[ S[i] ][ S[j] ] (cazul cel mai mic din dinamica ce poate fi rezolvat imediat).

Rezultatul se va gasi in din[ 1 ][ N ].
Complexitatea acestei dinamici este O(N³).