Pracowałem nad następującym problemem z tej książki .
Pewien język przetwarzania ciągów oferuje prymitywną operację, która dzieli ciąg na dwie części. Ponieważ ta operacja polega na skopiowaniu oryginalnego ciągu, n zajmuje ciąg n jednostek czasu o długości n, niezależnie od lokalizacji cięcia. Załóżmy teraz, że chcesz rozbić sznurek na wiele części. Kolejność wykonywania przerw może mieć wpływ na całkowity czas działania. Na przykład, jeśli chcesz wyciąć 20-znakowy ciąg znaków na pozycjach i , to wykonanie pierwszego cięcia na pozycji wiąże się z całkowitym kosztem , podczas gdy wykonanie pozycji 10 ma lepszy koszt .
Potrzebuję algorytmu programowania dynamicznego, który dał cięciom, znajdował minimalny koszt cięcia sznurka na kawałków.