Proces cięcia belki - programowanie dynamiczne

Byłbym wdzięczny, gdyby ktoś powiedział mi, czy ułożony przeze mnie algorytm jest poprawny oraz, jak zrealizować implementacyjnie optymalną listę cięć. Treść zadania jest następująca:

Proces cięcia belki na dwie krótsze części wymaga podniesienia tej belki, co jest pracą. Praca ta jest wprost proporcjonalna do długości kawałka. Ułóż algorytm tak, żeby pociąć belkę na daną ilość równych kawałków przy jak najmniejszej możliwej pracy (podnoszenie belki). Na wejściu dostajemy długość belki i liczbę równych kawałków na które mamy ja pociąć. Na wyjściu powinniśmy otrzymać całkowitą ilość wykonanej pracy oraz listę kolejności wykonywania cięć.

Mój algorytm:

int M; // liczba równych kawałków
int W[M+1] //minimalna praca dla danej długości belki liczonej w liczbie równych kawałków
W[0] = W[1] = 0;
for (int i = 2; i <=M; i++) W[i] = INT_MAX;

for(int d = 2; d <= M; d++){ // d - długość belki liczona w liczbie równych kawałków
	for(int k = 1; k < d; k++){ // k - miejsce cięcia
		int curWork = W[d-k] + W[k] + work(d);
		W[d] = min(W[d], curWork);
	}
}
return W[M];
 

1. Co to znaczy wprost proporcjonalna do długości kawałka? Jakiego kawałka? Całej aktualnej belki czy tego odkrawanego kawałka?
2. Mamy pociąć całą belkę?

Pewny jesteś że to jest zadanie na algorytm dynamiczny? Bo zasadniczo podstawowym kryterium dla algorytmów dynamicznych jest własność optymalnej podstruktury. To znaczy że znając rozwiązanie podproblemu mniejszego możemy łatwo wyznaczyć rozwiązanie problemu większego. Np. w problemie wydawania reszty, jeśli wiemy w jaki sposób optymalnie wydać wszystkie reszty od 0 do k-1 to możemy bez problemu policzyć jak optymalnie wydać k.
W twoim problemie nie widzę takiej własności. Bo nawet jeśli wiem jak optymalnie pociąć belkę na 0...k-1 kawałków to nijak nie pomaga mi to w stwierdzeniu jak pociąć ją na k kawałków bo przecież to będą zupełnie różne kawałki, skoro wszystkie mają być równe.

Ja bym raczej spodziewał się że ten problem rozwiązuje się jakąś wariacją na temat wyszukiwania połówkowego, bo dla odpowiednich danych połowienie na pewno będzie optymalnym rozwiązaniem.

Ad 1. Praca przy cięciu danego kawałka na pół jest prawdopodobnie równa długości całego przecinanego kawałka.
Ad 2. Tak, całą belkę na M równych kawałków.
Teraz rzeczywiście widzę, że przy algorytmie dynamicznym pojawia się problem z kolejnością cięcia (w tym z ułożeniem listy cięć). Czyli jak miałby wyglądać ten algorytm binarny? Iterujemy po kolei po wszystkich możliwych miejscach przecięcia belki na pół i za każdym razem wywołujemy funkcję znowu dla każdej z połówek?

Dobra, muszę przestać ćpać po nocy bo wypisuje głupoty a wy mnie jeszcze nie poprawiacie :P
Problem oczywiście ma optymalną podstrukturę co widać jak pomyślimy o połowieniu ->
Np. jeśli chcemy uzyskać podział na 6 części to połowimy i dostajemy 2 kawałki do podziału na 3. I teraz oba kawałki są symetryczne więc dzielimy je identycznie. Więc znając optymalny podział na 3 możemy od razu wyznaczyć optymalny podział na 6 ;]

Idea algorytmu jest dość prosta -> optymalnym podejściem jest dzielenie danego bloku na fragmenty które są jak najbardziej równe. Na podobnej zasadzie na jakiej działają algorytmy dziel i zwyciężaj typu merge sort.

1. Dla parzystego fragmentu optymalne jest dzielenie na pół.
2. Dla nieparzystego fragmentu optymalne jest dzielenie na dwa największe możliwe fragmenty które różnią się tylko o 1 (np. 7 = 4+3, 9 = 4+5) itd.

I teraz idea jest prosta, liczymy sobie koszty od 0 standardowo.
koszt[1] = 0
koszt[2] = koszt[1]+koszt[1]+1
koszt[3] = koszt[1]+koszt[2]+1
koszt[4] = koszt[2]+koszt[2]+1
koszt[5] = koszt[2]+koszt[3]+1
itd.
czyli koszt[x] = koszt[floor(x/2)]+koszt[ceil(x/2)]+1