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