Calcularea lui s, mv precum si actualizarea se pot face parcurgand de la j la k, complexitatea finala fiind cea mentionata mai sus.

Vrem sa coboram complexitatea la <tex>O(N*M^2^)</tex>. Valorile lui s si mv sunt usor de obtinut in O(M^2^) pe linie parcurgand subsecventele de coloane in modul corespunzator. Problema este cum actualizam ? Vom utiliza o dinamica auxiliara independenta de linii (care se refera doar la o singura linie la un moment dat).

Vrem sa coboram complexitatea la <tex>O(N*M^2^)</tex>. Valorile lui s si mv sunt usor de obtinut in <tex>O(M^2^)</tex> pe linie parcurgand subsecventele de coloane in modul corespunzator. Problema este cum actualizam ? Vom utiliza o dinamica auxiliara independenta de linii (adica una care se refera doar la o singura linie la un moment dat).

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