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?


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.