Minimum Cost to Cut a Stick
Anonymous
To find the minimum cost to cut a stick, use dynamic programming. First, sort the list of cut positions and add the start (0) and end positions of the stick. Then, use a DP table to calculate the minimum cost for each segment by considering every possible cut and adding the cost of making the cut plus the cost of cutting the resulting two segments. The final result will be in the DP table entry for the whole stick.
Check out your Company Bowl for anonymous work chats.