h1(#redu). 'Redu':problema/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^3^)$.