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_____

**i** ___S1___ **k** _____S2_____j

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

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] + din[k + 1][j] + C[ S[i] ][ S[k] ])$ pentru oricare $k=i,j$. Trebuie sa avem atentie la cateva cazuri particulare: