Điểm tối thiểu Tam giác của đa giác trong C ++

Giả sử chúng ta có một giá trị N, xét một đa giác N mặt lồi với các đỉnh có nhãn A [0], A [i], ..., A [N-1] theo chiều kim đồng hồ. Bây giờ, giả sử chúng ta muốn chia tam giác thành N-2 tam giác. Đối với mỗi tam giác, giá trị của tam giác đó là tích của nhãn các đỉnh và tổng điểm của tam giác sẽ là tổng các giá trị này trên tất cả N-2 tam giác trong tam giác. Chúng ta phải tìm tổng số điểm nhỏ nhất có thể mà chúng ta có thể đạt được với một số tam giác của đa giác. Vì vậy, nếu đầu vào là [1,2,3], thì đầu ra sẽ là 6, vì đa giác đã là tam giác và điểm của tam giác duy nhất là 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Tạo ma trận dp có kích thước 50 x 50, điền vào giá trị này bằng 0
n:=kích thước của mảng đã cho
cho l trong phạm vi n đến n
- đối với i:=0, j:=l - 1, khi j
  - cho k trong phạm vi i + 1 đến j - 1
    - nếu trong số dp [i, j] =0, thì
      - dp [i, j]:=tối thiểu của inf và dp [i, k] + dp [k, j] + A [i] * A [j] * A [k]
    - nếu không thì dp [i, j]:=tối thiểu của dp [i, j] và dp [i, k] + dp [k, j] + A [i] * A [j] * A [k]
trả về dp [0, n - 1]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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];
   }
};
main(){
   vector<int> v1 = {1,2,3};
   Solution ob;
   cout << (ob.minScoreTriangulation(v1));
}

Đầu vào

[1,2,3]

Điểm tối thiểu Tam giác của đa giác trong C ++

Ví dụ

Đầu vào

Đầu ra