Given a convex n-gon made by connecting a point sequence in this order, a triangulation of the convex n-gon is a way of dividing its interior into triangles without overlap.
First, we count the number of triangulations of a convex n-gon. We denote the number as : For example, .
Answer the values of , , and .
Represent as a function of , , , ..., and . We define and .
The following pseudo-code implements an algorithm for computing for arbitrary . Answer the code that fills [ ① ]. Also answer the computational complexity (order) of the algorithm.
C[2] = 1; C[3] = 1;
for(i=4...n)
C[i] = 0;
for(i=4...n)
for(j=0...i-3)
[ ① ]
return C[n];
Next, we find the triangulation of a convex n-gon with a minimum cost. Here, the cost of a triangulation is defined as the sum of the cost of triangles in the triangulation, and the cost of a triangle is defined as the sum of the cost of the edges composing the triangle. Assume that all (), the costs of the edges connecting an arbitrary pair of vertices () of the n-gon, are given.
We consider solving the problem of finding a triangulation with a minimum cost by dividing the problem into subproblems. We denote as the cost of triangulating a polygon made by a path starting from , visiting vertices clockwise, and then coming back to (see the figure below). Assume that are all given for and . Represent as a function of and . We define . Also draw a figure explaining the situation.
Give approximately 10-line pseudo-code implementing an algorithm to compute the minimum cost of triangulating an arbitrary n-gon using the formula obtained in (4). Also answer the computational complexity (order) of the algorithm.
Tomfluff's solution is wrong. Please refer to here to see his solution.
The original problem actually lacks an important assumption: . Without this assumption, % must be in the equation to prevent exceeding .
In the following we suppose the assumption holds.
题目实际上缺了一个假设：，如果没有这个假设，我们需要在 index 里包含 % 因为有可能超到 2n 去。下面我们认为题目给了这个假设。
In the figure given (a sub-polygon also a clockwisely arranged point sequence), any triangulation has a triangle including . This triangle has another node . So we can traverse .
在题目给的图（顺时针 sub-polygon）中，任意一种三角剖分必定有一个三角形包含 ，这个三角形另有一个节点 . 所以我们可以遍历 .
For any , the polygon is naturally divided into two clockwise point sequences: with vertices and with vertices which corresponds to E[i,k-i+1] and E[k,i+m-k] respectively.
Also, the triangulation cost in the sub-polygon has the created edge , which corresponds to D[i,i+m-1]; and two edges are connected when we choose corresponding to D[i,k] and D[k,i+m-1].
