बहुभुज लीटकोड सोल्यूशनचे किमान स्कोअर त्रिकोण


अडचण पातळी मध्यम
वारंवार विचारले उबेर
डायनॅमिक प्रोग्रामिंग

समस्या विधान

समस्येमध्ये ”किमान गुण त्रिकोणी of बहुभुजाकृती”आम्हाला व्हॅल्यू अ‍ॅरे दिला जातो जेथे अ‍ॅरेमधील प्रत्येक घटक घड्याळाच्या दिशेने लेबल केलेले असताना एन-साइड बहुभुजाचे मूल्य दर्शवितो.

बहुभुज एन -2 त्रिकोणांमध्ये त्रिकोणीकरण करणे हे आपले कार्य आहे. त्रिकोणाला त्रिकोण काढण्यासाठी गुण म्हणजे त्याच्या तीन शिरोबिंदूवरील मूल्यांचे उत्पादन. बहुभुज त्रिकोणाच्या एकूण स्कोअर म्हणजे सर्व त्रिकोणाच्या सर्व गुणांची बेरीज.

आम्हाला बहुभुजाच्या त्रिकोणाची किमान संख्या शोधावी लागेल.

उदाहरण

values = [1,3,1,4,1,5]
13

स्पष्टीकरण:  अशा प्रकारे बहुभुज त्रिकोणात काढल्यावर आम्हाला त्रिकोणीकरणासाठी किमान स्कोअर मिळेल:

1 * 1 * 3 + 1 * 1 * 4 + 1 * 1 * 5 + 1 * 1 * 1 = 13

बहुभुज लीटकोड सोल्यूशनच्या किमान स्कोअर त्रिकोणीकरता दृष्टिकोन

हे लक्षात ठेवून आम्हाला बहुभुज एन -2 त्रिकोणांमध्ये त्रिकोणाकृती बनवावे लागेल आणि त्रिकोण ओव्हरलॅपिंग होऊ नयेत. बहुभुजची प्रत्येक किनार जास्तीत जास्त एका त्रिकोणाचा भाग असू शकते कारण आच्छादित करण्यास परवानगी नाही.

तर बहुभुजची प्रत्येक धार एन -2 उर्वरित शिरोबिंदूसह त्रिकोण तयार करू शकते. खाली दिलेल्या प्रतिमेचा संदर्भ घ्या.

बहुभुज लीटकोड सोल्यूशनचे किमान स्कोअर त्रिकोण

 

जेव्हा आपण बहुभुजातून त्रिकोण कापतो तेव्हा आपल्यास नवीन लहान बहुभुज सोडले जाते. हे आम्हाला अशा क्षणापर्यंत नेले की आपण एखाद्या समस्येस छोट्या सबप्रोब्लम्समध्ये विभाजित करू शकतो.

बहुभुज लीटकोड सोल्यूशनचे किमान स्कोअर त्रिकोण

 

जर आपल्याला 0-6 पासून शिरोबिंदू असलेल्या बहुभुजासाठी किमान स्कोअर पाहिजे असेल तर नवीन सबप्रॉब्लम 0-3 आणि 3-6 मधील शिरोबिंदू असलेल्या बहुभुजासाठी किमान गुण आहे.

म्हणूनच रिकर्सिव्ह रिलेशनशिप बनतेः

minScore (pos1, pos2) = minScore (pos1, i, A) + minScore (i, pos2, A) + A [pos1] * A [pos2] * A [i]

पुन्हा पुन्हा त्याच सबप्रोब्लमच्या पुनरावृत्तीवर मात करण्यासाठी आम्ही एक मेमोरिझेशन टेबल वापरू. हे एक * एन अ‍ॅरे असेल जिथे i, j मधील मूल्य बहुभुजाची किमान स्कोअर त्रिकोणाकृती i ते j पर्यंत शिरोबिंदूमध्ये ठेवेल.

अंमलबजावणी

बहुभुज च्या किमान स्कोअर त्रिकोणासाठी सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
  int memo[51][51];
  
  int dp(int pos1,int pos2, vector<int>&A){
    if(pos2-pos1<=1)return 0;
    
    if(memo[pos1][pos2]!=-1)return memo[pos1][pos2];
    int ans=INT_MAX;
    for(int i=pos1+1;i<pos2;i++)
      ans=min(ans, dp(pos1,i,A) + dp(i,pos2,A) + A[pos1]*A[pos2]*A[i] );
    memo[pos1][pos2]=ans;
    return ans;
  }
  
  int minScoreTriangulation(vector<int>& A) {
    memset(memo,-1,sizeof(memo));
    return dp(0,A.size()-1,A);
  }
int main() 
{ 
 vector<int> arr = {1,3,1,4,1,5}; 
 cout<<minScoreTriangulation(arr)<<endl; 
 return 0;
}
13

बहुभुजाच्या किमान स्कोअर त्रिकोणासाठी जावा कोड

import java.util.Arrays; 
public class Tutorialcup {
    public static int minScoreTriangulation(int[] A) {
     return dp(A, 0, A.length - 1, new Integer[A.length][A.length]);
    }
    public static int dp(int[] A, int pos1,int pos2, Integer[][] memo){
    if(pos2-pos1<=1)return 0;
    
    if(memo[pos1][pos2] != null)return memo[pos1][pos2];
    int ans=Integer.MAX_VALUE;
    for(int i=pos1+1;i<pos2;i++)
      ans=Math.min(ans, dp(A,pos1,i,memo) + dp(A,i,pos2,memo) + A[pos1]*A[pos2]*A[i] );
    memo[pos1][pos2]=ans;
    return ans;
  }
  public static void main(String[] args) {
    int [] arr = {1,3,1,4,1,5}; 
    int ans= minScoreTriangulation(arr);
    System.out.println(ans);
  }
}
13

बहुभुज लीटकोड सोल्यूशनच्या किमान स्कोअर त्रिकोणाचे जटिल विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे ओ (एन * एन * एन) कारण बहुभुजाच्या त्रिकोणीकरणासाठी किमान स्कोअर देणार्‍या 3 वेगवेगळ्या आय, जे, के व्हॅल्यूजसाठी आम्ही व्हॅल्यू अ‍ॅरेचा शोध घेत आहोत. येथे n ही व्हॅल्यू अ‍ॅरेची लांबी आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (एन * एन) कारण लक्षात ठेवण्यासाठी एन * एन ची अतिरिक्त जागा वापरणे.

संदर्भ