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:

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. 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_____