Cho một số N, xem xét một đa giác lồi N cạnh với các đỉnh A[0], A[1], ..., A[N-1] theo chiều kim đồng hồ. Ta muốn chia đa giác thành N-2 tam giác. Giá trị của mỗi tam giác là tích các nhãn đỉnh, và tổng điểm của phép chia là tổng giá trị của N-2 tam giác. Tìm tổng điểm nhỏ nhất có thể đạt được.
Ví dụ: đầu vào [1,2,3], đầu ra là 6, vì đa giác đã là tam giác, điểm của tam giác duy nhất là 1*2*3 = 6.
Giải pháp sử dụng quy hoạch động:
Tạo ma trận dp kích thước 50x50, khởi tạo 0
n := kích thước mảng A
Với l từ 3 đến n (độ dài đoạn):
Với i từ 0, j = l-1; j < n; i++, j++:
Với k từ i+1 đến j-1:
dp[i][j] = min(dp[i][j] == 0 ? INT_MAX : dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j])Trả về dp[0][n-1]
Ví dụ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int minScoreTriangulation(vector<int>& A) { lli dp[50][50]; for(int i = 0; i < 50; i++){ for(int j = 0; j < 50; j++){ dp[i][j] = 0; } } int n = A.size(); for(int l = 3; l <= n; l++){ for(int i = 0, j = l - 1; j < n; i++, j++){ for(int k = i + 1; k < j; k++){ dp[i][j] = min(dp[i][j] == 0?INT_MAX : dp[i][j], dp[i][k] + dp[k][j] + 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)); }Đầu vào
[1,2,3]
Đầu ra
6