Problem
Assume we have a piece of wood (stick) and its length is M meter. There are N points on the wood and we want to cut the wood on those points and at the end, we would have N+1 pieces of wood. For example, consider the following: The length of the wood is 10, and we want to cut it in points x1=1, x2=3 and x3=6. At the end we will have 4 pieces. Now, assume the cost of cutting a wood with length L is the sum of the generated two pieces which would be L. In the above example, if we cut the wood from point x0 then we will have two pieces, one of the is 1 meter and the second would be 9 meters. So the total cost is 1+9=10. This cost is for one cut; the overall cost would be the sum of costs for cutting the wood through all points. In the previous example, if we cut the wood at first on x0 then x1 and finally x3 then the cost would be (1+9)+(2+7)+(3+4)=26, The goal is to find an optimal order of points for cutting the wood (having the minimum cost). Propose an algorithm using dynamic programming to solve this problem. Try to trace and show all the steps through the given example. Explain all the details of the algorithm. Your algorithm should find the minimum cost as well as the optimal order of cutting points. What is the time complexity of your algorithm?