Exercise 4. DYNAMIC PROGRAMMING. Suppose that we are given the coordinates of the n vertices of a

convex n-sided polygon. We are to triangulate the polygon by drawing n - 3 nonintersecting diagonals,

where a diagonal is a line segment that connects two non-adjacent vertices. The value of a triangulation

is the sum of the lengths of the n-3 diagonals. A triangulation is optimal if it minimizes this value.

The objective is to find an optimal triangulation as described by its n-3 diagonals. Show how dynamic

programming leads to an O(n³) time solution, assuming a RAM model of computation.