returnează Tm[M][0];
==

Mai există două optimizări de spaţiu pe care le putem efectua în soluţia prezentată. Putem elimina matricea $T{~um~}$, calculând toate valorile direct pe matricea $T{~m~}$, deoarece aceasta va fi parcursă în ambii paşi în câte o singură direcţie. A doua optimizare se bazează pe observaţia că nu avem niciodată nevoie de alte linii în afară de ultimele 2 ({$i$} si {$i-1$}), deci putem înlocui matricea cu 2 vectori de dimensiune $2^N^$. Valorile $T{~t~}$ pot fi calculate în cadrul primei bucle, reducând astfel spaţiul necesar soluţiei la $O(2^N^)$.

Mai există două optimizări de spaţiu pe care le putem efectua în soluţia prezentată. Putem elimina matricea $T{~um~}$, calculând toate valorile direct pe matricea $T{~m~}$, deoarece aceasta va fi parcursă în ambii paşi în câte o singură direcţie. A doua optimizare se bazează pe observaţia că nu avem niciodată nevoie de alte linii în afară de ultimele 2 ($i$ si $i-1$), deci putem înlocui matricea cu 2 vectori de dimensiune $2^N^$. Valorile $T{~t~}$ pot fi calculate în cadrul primei bucle, reducând astfel spaţiul necesar soluţiei la $O(2^N^)$.