Computers and Technology
Dynamic Programming:To cut a n centimeter long gold bar into two pieces costs $n. When a gold bar is cut into manypieces, the order in which the cuts occur can affect the total amount of costs. For example, to cut a20 centimeter gold bar at length marks 2, 8, and 10 (numbering the length marks in ascending orderfrom the left-hand end, starting from 1). If the cuts to occur in left-to-right order, then the first cutcosts $20, the second cut costs $18 (cutting the remaining 18 centimeter bar at originally lengthmark 8), and the third cut costs $12, totaling $50. If the cuts to occur in right-to-left order, however,then the first cut costs $20 time, the second cut costs $10, and the third cut costs $8, totaling $38.In yet another order, the first cut is at 8 (costing $20), then the 2nd cut is at 2 (costing $8), andfinally the third cut is at 10 (costing $12), for a total cost of $40. Given a n centimeter long goldbar G and an array C[1..m] containing the cutting points in ascending order):(1) Formulate the recursive relation of the optimal solution;(2) Design a bottom-up algorithm to calculate the lowest cost for a sequence of cuts;(3) Analyze the complexity of your algorithm;(4) Write an algorithm to print out a sequence of cuts that achieves this cost.