leetcode 1039

问题

Given N, consider a convex N-sided polygon with vertices labelled A[0], A[i], ..., A[N-1] in clockwise order.

Suppose you triangulate the polygon into N-2 triangles. For each triangle, the value of that triangle is the product of the labels of the vertices, and the total score of the triangulation is the sum of these values over all N-2 triangles in the triangulation.

Return the smallest possible total score that you can achieve with some triangulation of the polygon.

Example 1:

1
2
3
Input: [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.

Example 2:

img

1
2
3
Input: [3,7,4,5]
Output: 144
Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.  The minimum score is 144.

Example 3:

1
2
3
Input: [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

Note:

  1. 3 <= A.length <= 50
  2. 1 <= A[i] <= 100

分析

多边形中每条边都是被划分完之后的三角形的一个底，我们可以先固定一个边，当确定一个三角形之后，剩下的部分就被分成两个多边形（子问题）。这样我们先确定一个边，然后遍历其另一个顶点可能出现的位置，这样就可以利用子问题来得到这个多边形的总问题。为了方便遍历，我们每次固定边都选择index 最大的点和index 最小的点所组成的那条边进行遍历。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 自顶向下的方式
class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        return helper(A, dp, 0, n-1);
    }
    int helper(vector<int> &A, vector<vector<int>> &dp, int i, int j) {
        if (dp[i][j] != 0)
            return dp[i][j];
        int ret = 0;
        for (int k = i+1; k < j; ++k) {
            ret = min(ret==0? INT_MAX: ret,
                A[i]*A[j]*A[k] + helper(A, dp, i, k) + helper(A, dp, k, j));
        }
        return dp[i][j] = ret;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 自底向上
class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i+len-1 < n; ++i) {
                int j = i+len-1;
                for (int k = i+1; k < j; ++k) {
                    dp[i][j] = min(dp[i][j]==0? INT_MAX: dp[i][j],
                                  A[i]*A[j]*A[k] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};