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


कठिनाई तह मध्यम
बारम्बार सोधिन्छ Uber
डायनामिक प्रोग्रामिंग

समस्या बयान

समस्यामा "न्यूनतम स्कोर Triangulation of पोलिगन"हामीलाई एउटा मान एर्रे दिइन्छ जहाँ एरेमा प्रत्येक एलिमेन्टले एन-साइड साइड बहुभुजाको मान प्रतिनिधित्व गर्दछ जब घडीको दिशामा लेबल गरिन्छ।

हाम्रो कार्य बहुभुजलाई एन -२ त्रिकोणमा त्रिकोणित गर्नु हो। एक त्रिकोण त्रिकोणित करने के लिए अंक इसके तीन शिरोबिन्दु मा मानको उत्पादन हो। बहुभुज त्रिकोणित गर्नका लागि कुल स्कोर सबै त्रिकोणको सबै स्कोरहरूको योग हो।

हामीले बहुभुजको त्रिकोणको न्यूनतम स्कोर पाउनु पर्छ।

उदाहरणका

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

व्याख्या:  हामी त्रिकोणको लागि न्यूनतम स्कोर प्राप्त गर्नेछौं, जब हामी बहुभुजलाई यसरी त्रिकोणमा पार्छौं:

१ * १ * + + १ * १ * + + १ * १ * + + १ * १ * १ = १ 1

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

यो दिमागमा राख्दै हामीले बहुभुजलाई एन -२ त्रिकोणमा त्रिकोणित गर्नुपर्नेछ र त्रिकोण ओभरल्यापि not हुनुहुन्न। बहुभुजको प्रत्येक किनारा अधिकतम एक त्रिकोणको एक हिस्सा हुन सक्छ किनकि ओभरल्यापि .लाई अनुमति छैन।

त्यसैले बहुभुजको प्रत्येक किनाराले त्रिकोण बनाउँदछ N-2 बाँकी ठाडोसँग। तलको चित्रमा सन्दर्भ गर्नुहोस्।

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

 

जब हामी बहुभुजबाट त्रिकोण काट्छौं हामी नयाँ सानो बहुभुजको साथ बाँकी हुन्छौं। यसले हामीलाई यस्तो बिन्दुमा पुर्‍यायो कि हामी समस्यालाई सानो उप-समस्याहरूमा विभाजित गर्न सक्छौं।

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

 

त्यसोभए यदि हामी ०- from बाट भर्टेक्स भएको बहुभुजको लागि न्यूनतम स्कोर चाहान्छौं भने नयाँ सबप्रोब्लम ० -। र 0- from बाट शीर्षको साथ बहुभुजको लागि न्यूनतम स्कोर हो।

त्यसैले पुनरावर्ती सम्बन्ध हुन्छ:

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

उही सबप्रोब्लमको पुन: गणनामाथि विजय पाउन हामी फेरि कण्ठ गर्ने तालिका प्रयोग गर्नेछौं। यो एक * n एर्रे हुनेछ जहाँ i, j मा मानले बहुभुजको न्यूनतम स्कोर त्रिकोणनलाई i देखि j सम्म ठाडोसँग भण्डार गर्दछ।

कार्यान्वयन

बहुभुजको न्यूनतम स्कोर त्रिकोणको लागि C ++ कोड

#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

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

समय जटिलता

माथिको कोडको समय जटिलता हो O (n * n * n) किनकि हामी different अलग प्रकारको i, j, k मानहरूको लागि मूल्य एर्रे ट्रैभर्स गर्दैछौं जुन बहुभुजको त्रिकोणको लागि न्यूनतम स्कोर दिन्छ। यहाँ n मान एर्रे को लम्बाई छ।

ठाउँ जटिलता

माथिको कोडको स्पेस जटिलता हो O (n * n) किनभने यादगारको लागि n * n अतिरिक्त ठाउँ प्रयोग गर्दै।

सन्दर्भ