मान लीजिए हमारे पास एक मान N है, एक उत्तल N-भुजा बहुभुज पर विचार करें जिसके शीर्ष A[0], A[1], ..., A[N-1] दक्षिणावर्त क्रम में लेबल किए गए हैं। अब मान लीजिए हम इस बहुभुज को N-2 त्रिभुजों में त्रिभाजित (triangulate) करना चाहते हैं। प्रत्येक त्रिभुज का मान उसके शीर्षों के लेबल का गुणनफल होता है, और त्रिभाजन का कुल स्कोर सभी N-2 त्रिभुजों के मानों का योग होता है। हमें किसी त्रिभाजन के साथ प्राप्त होने वाले सबसे छोटे संभव कुल स्कोर को खोजना है।
उदाहरण के लिए, यदि इनपुट [1,2,3] है, तो आउटपुट 6 होगा, क्योंकि बहुभुज पहले से ही त्रिभाजित है, और एकमात्र त्रिभुज का स्कोर 6 है।
समाधान दृष्टिकोण
आकार 50x50 का एक dp मैट्रिक्स बनाएं, 0 से भरें
n := दिए गए ऐरे का आकार
लंबाई l = 3 से n तक लूप चलाएं
सभी संभावित i, j जोड़ों के लिए, k को i+1 से j-1 तक बदलते हुए न्यूनतम स्कोर की गणना करें
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) {
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));
return 0;
}
इनपुट
[1,2,3]
आउटपुट
6
