Dynamic Programming - Cutting Sticks - Tiago - Medium

8/28/2019 Dynamic Programming: Cutting Sticks - Tiago - Medium
Dynamic Programming: Cutting Sticks

Tiago
Jan 8 · 4 min read
This article will walk you through a problem called Cutting Sticks¹ from UVA
(Universidad de Valladolid)’s problem set². Read the original problem before
continuing this article.
We have a stick (wood) that needs to be cut:
The cuts must be done in certain parts of the stick. You must cut the stick in all marked
places. For example, consider a stick of size 10 and 3 places marked in it (positions 2, 4
and 7) where the cuts must be made.
The cost to make a cut is the same as the size of the stick. For instance, if you have a
stick of size 10 and you need to make one cut (anywhere) in it, that will cost you 10.
It is not difficult to notice that depending on the order you perform the cuts, your total
cost will be different. For example, if you cut the stick on positions 2, 4 and 7 (in this
order), the total cost will be 10+8+6=24. A better way to cut that stick would be by
starting on position 4, then 2 then 7. That would yield a cost of 10+4+6=20,
https://medium.com/@tiagot/dynamic-programming-cutting-sticks-93415f1ad2ec 1/5
Example of 2 ways to perform the cuts. Notice the one on the right is better than the left one as the total
cost to perform all 3 cuts is smaller.
The problem asks you to find the minimum possible cost given the size of the stick and
the places where it needs to be cut.
Let’s define a few things:
N: The size of the original stick
k: The position (index) where a generic cut is made.
optimalCost(initialIndex, endIndex) : A function that returns the best cost to cut a
stick that starts in initialIndex and ends in endIndex .
Notice that we want to find optimalCost(0, N) .
Here is the key observation to solve this problem. Whenever we make a cut, we divide
the stick into 2 other sticks. Those 2 new sticks will then need to be cut again (if there
is a cut to be made on it) or will remain intact (if there is no further cutting to be
made). Notice that those 2 new sticks that need to be cut represent the same problem
again, except that now we have a new stick with a new size and new places (i.e, new
indexes) to cut it. With that in mind, we just need to find the best way to cut those 2
new sub-sticks and sum their cost with the cost of the original cut you made.
We can equate the above like this:
optimalCost(initialStickPosition, endStickPosition) =
optimalCost(initialStickPosition, k) +
optimalCost(k, endStickPosition) +
sizeOfTheCurrentStick
Here 'k’ is one of the original positions where the stick should be cut.
We also have that sizeOfTheCurrentStick = endStickPosition — initialStickPosition
so the final recursive formula is:
optimalCost(initialStickPosition, endStickPosition) =
optimalCost(initialStickPosition, k) +
optimalCost(k, endStickPosition) +
(endStickPosition - initialStickPosition)
Now we only have to loop through all possible places where the cut can be made (i.e,
all possible 'k's )and select the one that yields the minimum cost:
1 int bestCut = INF

2 for(int k=indexOfFirstCut, k<=indexOfLastCut, k=nextCutIndex()){
3 int subCutCost = optimalCost(0, N, k);
4 if(subCutCost < bestCut){
5 bestCut = subCutCost;
6 }
7 }
8
9 int optimalCost(int initialStickPosition,
10 int endStickPosition,
11 int k){
12 return optimalCost(initialStickPosition, k) +
13 optimalCost(k, endStickPosition) +
14 (endStickPosition - initialStickPosition)
15 }
optimalCut java hosted with ❤ by GitHub view raw

Coding nextCutIndex() is trivial and there are many ways to do it, so I won’t pollute the
code in this article with it.
With the above, the problem is technically solved, but there is one issue with it: a lot of
sub-problems will be recalculated over and over again, making our program slow. That
is where Dynamic Programming can help us. All we have to do is to store the best cut
for the sub-sticks we have found. Then, the next time we need to find its value, we can
just look it up without having to go through the recursion again:
1 int optimalCost(int initialStickPosition,

2 int endStickPosition,
3 int k){
4
5 int memorizedResult = m[initialStickPosition][endStickPosition];
6 if(memorizedResult != INF){
7 return memorizedResult;
8 }
9 int bestCost = optimalCost(initialStickPosition, k) +
10 optimalCost(k, endStickPosition) +
11 (endStickPosition - initialStickPosition)
12
13 m[initialStickPosition][endStickPosition] = bestCost;
14 return bestCost;
15 }
optimalCut memorization java hosted with ❤ by GitHub view raw
Here ’m’ is our matrix that will hold the best costs already calculated. If you don’t do
this memorisation step and you try to submit your code on the UVA website, you will
get a Time limit exceeded error, meaning your program is too slow to process all test
cases they have.
Notice the approach we have taken is a top-down one because we start the recursion
with the highest stick possible and proceed on cutting it into sub-sticks until there is
nothing more to cut. Sometimes it is easier to think about a DP problem this way.
Nothing stops you from using a bottom-up approach though (as we have done in our
first DP article³).
You can find my full C++ implementation here⁴.
Sources:
1. “Cutting Sticks”: https://uva.onlinejudge.org/index.php?

option=com_onlinejudge&Itemid=8&page=show_problem&problem=944
2. UVA’s problem set index: https://uva.onlinejudge.org/index.php?

option=com_onlinejudge&Itemid=8
3. “Dynamic Programming: An induction approach”:

https://medium.com/@tiagot/dynamic-programming-an-induction-approach-
b5c5e73c4a19
4. Complete solution: https://github.com/TheCoinTosser/Competitive-

Programming/blob/c3e390a4b7bda82cd6479dfe52d22c7ed3dab405/UVA/1000
3__Cutting_Sticks.cpp
Programming
About Help Legal

Dynamic Programming - Cutting Sticks - Tiago - Medium

Uploaded by

Copyright:

Available Formats

Dynamic Programming - Cutting Sticks - Tiago - Medium

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dynamic Programming - Cutting Sticks - Tiago - Medium

Uploaded by

Copyright:

Available Formats

8/28/2019 Dynamic Programming: Cutting Sticks - Tiago - Medium

Dynamic Programming: Cutting Sticks

We have a stick (wood) that needs to be cut:

Let’s define a few things:

N: The size of the original stick

k: The position (index) where a generic cut is made.

optimalCost(initialIndex, endIndex) : A function that returns the best cost to cut a

stick that starts in initialIndex and ends in endIndex .

Notice that we want to find optimalCost(0, N) .

We can equate the above like this:

We also have that sizeOfTheCurrentStick = endStickPosition — initialStickPosition

so the final recursive formula is:

1 int bestCut = INF

optimalCut java hosted with ❤ by GitHub view raw

1 int optimalCost(int initialStickPosition,

optimalCut memorization java hosted with ❤ by GitHub view raw

You can find my full C++ implementation here⁴.

1. “Cutting Sticks”: https://uva.onlinejudge.org/index.php?

2. UVA’s problem set index: https://uva.onlinejudge.org/index.php?

3. “Dynamic Programming: An induction approach”:

4. Complete solution: https://github.com/TheCoinTosser/Competitive-

About Help Legal

You might also like