Une image $3\times 4$, à la main

Énergies. Par exemple le pixel intérieur $(1,1)$, de niveau $80$, a quatre voisins à $80$ et quatre à $10$ : $e(1,1)=4\times 70/8=35$. Le coin $(0,0)$, de niveau $80$, a pour voisins $(0,1)=80$, $(1,0)=10$, $(1,1)=80$ : $e(0,0)=70/3=23$ (division entière).

$$E=\begin{array}{ccccc}l=2& 23& 42& 28& 23\\ l=1& 42& 35& 35& 42\\ l=0& 23& 28& 42& 23\end{array}M=\begin{array}{ccccc}l=2& 81& 100& 86& 81\\ l=1& 65& 58& 58& 65\\ l=0& 23& 28& 42& 23\end{array}$$

Tableau $M$. Ligne $0$ : $m(0,c)=e(0,c)$. Ligne $1$ : par exemple $m(1,1)=\min \{23,28,42\}+35=58$. Ligne $2$ : $m(2,0)=\min \{65,58\}+23=81$.

Couture. Le minimum de la dernière ligne vaut $81$, atteint en colonne $0$ (et aussi en colonne $3$ : deux coutures sont optimales). On remonte : $(2,0)$ vient de $(1,1)$ ($58<65$), qui vient de $(0,0)$ ($23<28$). Couture $(0,0)\to (1,1)\to (2,0)$, de coût $23+35+23=81$.

nom : M
valeurs : 81 100 86 81
vert : 0 3
legende : ligne l = 2 de M : minimum 81, en colonne 0 et en colonne 3

couture (colonnes, ligne 0 d'abord) : [0, 1, 0], coût 81
Image réduite :
l=2 [10, 80, 80]
l=1 [10, 80, 10]
l=0 [80, 10, 10]