1039. 多邊形三角剖分的最低得分

思路

現在有n邊形，要拆成多個三角形，給出最小的分數。
在兩個點的情況，無法形成三角形，答案為0。
在三角形的狀況，只能將現存的三個點連起來。
在四邊形的情況，能將第0跟第2個點相連，或是第1跟第3個點相連。

在五邊形的情況，能相連0-2、0-3、\

• 相連0-2，形成0-1-2的三角形，以及2-3-4-0的四邊形，\
• 相連0-3，形成0-1-2-3的四邊形，和3-4-0的三角形

在六邊形的情況，相連0-2、0-3、0-4

• 相連0-2，形成0-1-2的三角形，以及2-3-4-5-0的邊形，
• 相連0-3，形成0-1-2-3的四邊形，和3-4-5-0的四邊形。
• 相連0-4，形成0-1-2-3-4的五邊形，和4-5-0的三角形。

利用一個dfs函數找到答案，參數i,j代表相連的起點與終點，用記憶化搜索記住已經算過的數值。

在n邊形的情況，可以相連0~2到0~n-1。

• 相連0~i，形成一個i + 1邊形，和一個n - i + 1邊形，後者最後會連回起點， 像是3-4-5-0的四邊形，能先算好dfs(3,5)，再加上0-3-5這個三角形。

因為一個問題能被拆成更小的子問題，能轉換成動態規劃。

• 因為i<k<j，而

// 迴圈略去
dp[i][j] = min(dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]);

因此dp[i][k]和dp[k][j]得先算好，

• k > i，所以i得倒過來遍歷，能從n-3開始（形成三角形的最小邊數）
• j > k，j 正序遍歷。從i + 2開始（理由同上）

程式碼

1. 記憶化搜索

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> f(n, vector<int>(n));
        auto dfs = [&](this auto&& dfs, int i, int j) {
            int& res = f[i][j]; // 使用引用。
            if(res) {
                return res;
            }
            if(j - i == 1) { // 終止條件，兩個相鄰的點無法形成三角形
                return 0;
            }
            res = INT_MAX;
            for(int k = i + 1; k < j; ++k) { // 起點連上除終點外的所有點。
                res = min(res, dfs(i, k) + dfs(k, j) + values[i] * values[j] * values[k]);
            }
            return res;
        };
        return dfs(0, n - 1);
    }
};

2. 動態規劃

class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();
        vector<vector<int>> f(n, vector<int>(n));
        for(int i = n - 3; i >= 0; --i) {
            for(int j = i + 2; j < n; ++j) {
                f[i][j] = INT_MAX;
                for(int k = i + 1; k < j; ++k) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        return f[0][n - 1];
    }
};

判斷複雜度

• 時間複雜度：$O(n^3)$
• 空間複雜度：$O(n^2)$