Rozwiązanie przez programowanie dynamiczne:

Niech l_0, l_1, ... , l_n to długości kolejnych fragmentów belki, które mamy otrzymać na końcu.
Zdefiniujmy tablicę T[i,j], dla 0<=i<j<=n, następująco: T[i,j] to optymalny koszt pocięcia
belki długości l_i+l_{i+1}+...+l_{j} na belki długości l_i, l_{i+1}, ... , l_j.
Łatwo zauważyć, że T[i,j] spełnia następujące własności rekurencyjne:
 (1) T[i,i] = 0 dla kaĹźdego i;
 (2) jeśli i<j, to T[i,j] = L + max_{i<=k<j} (T[i,k]+T[k+1,j]), gdzie L = l_i+l_{i+1}+...+l_{j}.
Drugi wzór wynika z tego, że rozważamy wszystkie możliwe przypadki, gdzie możemy wykonać 
pierwsze cięcie, a potem rozwiązujemy optymalnie obie otrzymane krótsze belki patrząc do
już obliczonych wartości w tablicy T.

Przy pomocy wzorów (1) i (2) możemy policzyć wszystkie wartości T[i,j] w czasie O(n^3).
Szukany rezultat to T[0,n].