Optimal Rod Division Cost

You are given a wooden rod of length rodLength units. The rod is conceptually marked from position 0 to position rodLength, representing a continuous segment that can be divided at any integer position along its length.

You are also provided with an integer array divisionPoints, where each divisionPoints[i] represents a specific position where you must make a cut to divide the rod. All positions in the array are unique and fall strictly within the range (0, rodLength).

The Division Process:

• When you divide a rod segment, the cost incurred equals the current length of that segment.
• After a division at position p, the original segment splits into two smaller segments.
• You must continue making divisions until all specified positions have been processed.
• The order in which you perform the divisions can be chosen freely—there is no mandatory sequence.

Your Objective: Determine the minimum total cost required to complete all divisions at the specified positions. Since the order of divisions affects the cumulative cost, you must find the optimal sequence that minimizes the sum of all individual division costs.

Understanding the Cost Mechanics: Consider a rod of length 7 with division points [1, 3, 4, 5]:

• If you divide in the order [1, 3, 4, 5], you first divide the full rod (cost 7), then the segment from 1-7 (cost 6), then 3-7 (cost 4), then 4-7 (cost 3). Total: 7 + 6 + 4 + 3 = 20.
• However, if you reorder divisions to [3, 5, 1, 4], the costs become: 7 + 4 + 3 + 2 = 16, which is optimal.

The key insight is that dividing at the middle of remaining segments tends to produce smaller sub-segments earlier, reducing subsequent costs. Your task is to find this optimal ordering efficiently.