Problème — Découpe d'une barre (rod cutting)

Soit $R(\ell )$ le revenu maximal pour une barre de longueur $\ell$. On a $R(\ell )={\max }_{1\le i\le \ell }(\text{prix}[i]+R(\ell -i))$, avec $R(0)=0$.

def decoupe_barre(prix, n):
    # prix indexe de 1 a n ; on suppose prix[0] = 0
    R = [0] * (n + 1)
    for longueur in range(1, n + 1):
        meilleur = float('-inf')
        for i in range(1, longueur + 1):
            meilleur = max(meilleur, prix[i] + R[longueur - i])
        R[longueur] = meilleur
    return R[n]

La complexité est $O(n^2)$. Ce problème illustre parfaitement la sous-structure optimale : la meilleure découpe d'une barre se déduit des meilleures découpes des morceaux plus courts.