ধরুন আমাদের একটি মান N আছে, A[0], A[i], ..., A[N-1] লেবেলযুক্ত শীর্ষবিন্দু সহ একটি উত্তল N-পার্শ্বযুক্ত বহুভুজ বিবেচনা করুন। এখন ধরুন আমরা বহুভুজটিকে N-2 ত্রিভুজে ত্রিভুজ করতে চাই। প্রতিটি ত্রিভুজের জন্য, সেই ত্রিভুজের মান হল শীর্ষবিন্দুগুলির লেবেলের গুণফল, এবং ত্রিভুজটির মোট স্কোর হবে ত্রিভুজের সমস্ত N-2 ত্রিভুজের উপর এই মানের সমষ্টি। বহুভুজের কিছু ত্রিভুজ দিয়ে আমরা অর্জন করতে পারি এমন ক্ষুদ্রতম সম্ভাব্য মোট স্কোর আমাদের খুঁজে বের করতে হবে। সুতরাং যদি ইনপুটটি [1,2,3] হয়, তাহলে আউটপুট হবে 6, যেহেতু বহুভুজটি ইতিমধ্যেই ত্রিভুজ করা হয়েছে এবং একমাত্র ত্রিভুজের স্কোর হল 6৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
50 x 50 আকারের একটি ম্যাট্রিক্স ডিপি তৈরি করুন, এটি 0
দিয়ে পূরণ করুন -
n :=প্রদত্ত অ্যারের আকার
-
l এর জন্য n থেকে n
পরিসরে-
i এর জন্য :=0, j :=l – 1, যখন j
-
k এর জন্য i + 1 থেকে j – 1
পরিসরে-
যদি dp[i, j] =0 হয়, তাহলে
-
dp[i, j] :=ন্যূনতম inf এবং dp[i, k] + dp[k, j] + A[i] * A[j] * A[k]
-
-
অন্যথায় dp[i, j] :=ন্যূনতম dp[i,j] এবং dp[i, k] + dp[k, j] + A[i] * A[j] * A[k]
-
-
-
-
রিটার্ন dp[0, n – 1]
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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));
} ইনপুট
[1,2,3]
আউটপুট
6
