Minimum Score Triangulation of Polygon ใน C++

คำอธิบายปัญหา

กำหนดรูปหลายเหลี่ยมคAVE N ด้าน มีจุดยอด A[0] ถึง A[N-1]เรียงตามเข็มนาฬิกา ต้องการแบ่งสามเหลี่ยม (Triangulation) ได้ N-2 สามเหลี่ยม คะแนนของแต่ละสามเหลี่ยม = ผลคูณของเลขที่จุดยอด 3 จุด คะแนนรวม = ผลรวมคะแนนทุกสามเหลี่ยม ต้องการหาคะแนนรวมต่ำสุดที่เป็นไปได้

ตัวอย่าง: [1,2,3] → 6 (เพียงสามเหลี่ยมเดียว 1×2×3=6)

วิธีแก้ปัญหา (Dynamic Programming)

1. dp[i][j] = คะแนนต่ำสุดสำหรับรูปหลายเหลี่ยมจากจุดยอด i ถึง j
2. ฐาน: dp[i][i+1] = 0 (ไม่ใช่สามเหลี่ยม)
3. สำหรับความยาว l = 3 ถึง N:
4. วน i จาก 0 ถึง N-l, j = i+l-1
5. ลองจุด k ระหว่าง i+1 ถึง j-1 เป็นจุดยอดกลาง
6. dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i]*A[k]*A[j])
7. คำตอบ = dp[0][N-1]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;

class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
        int n = A.size();
        vector<vector<lli>> dp(n, vector<lli>(n, 0));
        
        for(int l = 3; l <= n; l++) {
            for(int i = 0, j = l - 1; j < n; i++, j++) {
                dp[i][j] = LLONG_MAX;
                for(int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j], 
                        dp[i][k] + dp[k][j] + (lli)A[i] * A[k] * A[j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

int main() {
    vector<int> v1 = {1,2,3};
    Solution ob;
    cout << ob.minScoreTriangulation(v1);
    return 0;
}

อินพุต

[1,2,3]

เอาต์พุต

6