1
$\begingroup$

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost.

Example: There's a stick of length 100, with cutting points at 25, 50 and 80 (so n = 3). Consider two ways to cut it.

The first way, we make a cut at 25 (with cost 100), then at 50 (with cost 75 - the stick we're cutting has length 75), then at 80 (with cost 50). Total cost: 225.

The second (optimal) way would be to cut succesively at 50 (cost 100), 20 (cost 50) and 80 (cost 50), for total cost 200.

There exists an $O(n^3)$ DP algorithm. First, we use an array A to save the endpoints and the cuttingpoints (in this case 0 through 4, with 0 and 4 being the endpoints), so $A = (0, 25, 50, 80, 100)$.

Use the following recursion:

$\text{min_cost}(i, i + 1) = 0$ and $\text{min_cost}(i, j) = A[j] - A[i] + \min( \text{min_cost}(i,k) + \text{min_cost}(k,j) : i < k < j)$

The final answer would be $\text{min_cost}(0, n+1)$

Every calculation of $\text{min_cost}(i, j)$ is $O(n)$, and we need to calculate $O(n^2)$ values, so this algorithm is $O(n^3)$.

To my actual question: I've read that the Knuth Yao DP speedup could make it $O(n^2)$. I've tried to look it up, but I can't find a good explanation what it is (I've found some short explanations which are too short, and don't help me understand it).

Could anyone explain it to me, preferably with a bit of pseudocode?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.