I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem
You have to cut a metal pipe into several pieces. To do so, you bring it to a company that charges money according to the length of the pipe being cut. Their cutting method means that only one cut can be made at a time.
Different ways in cutting the pipe can lead to different overall total prices. For example, suppose that a pipe of length 10 meters has to be cut at 2, 4, and 7 meters from one end. There are several ways to do this. One way is to first cut at 2, then 4, and then at 7. This gives a price of 10 + 8 + 6 = 24 because the first pipe was 10 meters in length, the second was 8 meters, and the third was 6 meters in length. Another way is to cut at 4, then at 2, then at 7. This would give a total price of 10 + 4 + 6 = 20, which is a cheaper price.
Figure out (a method to determine) what is the cheapest price that is possible (to make sure that the company isn't cheating you). The procedure that you write (in Java) should return a single integer, which will be the cheapest possible total cost for performing all of the cuts. Only one cut can be performed at a time, and the cost of making a cut is equal to the length of the pipe being cut (before the cut is performed).
But I'm having trouble knowing where I even need to start. If anyone could point me in the direction of where I can research similar problems or give me an idea of what I should be thinking about with this problem it would be great.