పాలిగాన్ లీట్‌కోడ్ సొల్యూషన్ యొక్క కనీస స్కోరు త్రిభుజం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది ఉబెర్
డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

సమస్యలో ”కనీస స్కోరు ట్రియాంగులేషన్ of పాలిగాన్”మాకు విలువ శ్రేణి ఇవ్వబడుతుంది, ఇక్కడ శ్రేణిలోని ప్రతి మూలకం సవ్యదిశలో లేబుల్ చేయబడినప్పుడు N- వైపుల బహుభుజి విలువను సూచిస్తుంది.

బహుభుజిని N-2 త్రిభుజాలుగా త్రిభుజం చేయడమే మా పని. త్రిభుజాన్ని త్రిభుజం చేసే స్కోరు దాని మూడు శీర్షాల వద్ద విలువల యొక్క ఉత్పత్తి. బహుభుజిని త్రిభుజం చేయడానికి మొత్తం స్కోరు అన్ని త్రిభుజం యొక్క అన్ని స్కోర్‌ల మొత్తం.

బహుభుజి యొక్క త్రిభుజం యొక్క కనీస స్కోరును మనం కనుగొనాలి.

ఉదాహరణ

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

వివరణ:  మేము బహుభుజిని ఈ విధంగా త్రిభుజం చేసినప్పుడు మేము త్రిభుజాకారానికి కనీస స్కోరును పొందుతాము:

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

పాలిగాన్ లీట్‌కోడ్ సొల్యూషన్ యొక్క కనీస స్కోరు త్రిభుజం కోసం విధానం

మనం బహుభుజిని N-2 త్రిభుజాలుగా త్రిభుజం చేయవలసి ఉందని మరియు త్రిభుజాలు అతివ్యాప్తి చెందకూడదని గుర్తుంచుకోండి. అతివ్యాప్తి అనుమతించబడనందున బహుభుజి యొక్క ప్రతి అంచు గరిష్టంగా ఒక త్రిభుజంలో భాగం కావచ్చు.

కాబట్టి బహుభుజి యొక్క ప్రతి అంచు N-2 మిగిలిన శీర్షాలతో ఒక త్రిభుజాన్ని ఏర్పరుస్తుంది. క్రింద ఉన్న చిత్రాన్ని చూడండి.

పాలిగాన్ లీట్‌కోడ్ సొల్యూషన్ యొక్క కనీస స్కోరు త్రిభుజం

 

మేము బహుభుజి నుండి ఒక త్రిభుజాన్ని కత్తిరించినప్పుడు మనకు క్రొత్త చిన్న బహుభుజి మిగిలి ఉంటుంది. ఇది ఒక సమస్యను చిన్న ఉప సమస్యలుగా విభజించగల స్థితికి దారితీసింది.

పాలిగాన్ లీట్‌కోడ్ సొల్యూషన్ యొక్క కనీస స్కోరు త్రిభుజం

 

కాబట్టి 0-6 నుండి శీర్షంతో బహుభుజికి కనీస స్కోరు కావాలంటే, కొత్త ఉపప్రాబ్లమ్ 0-3 మరియు 3-6 నుండి శీర్షంతో బహుభుజికి కనీస స్కోరు.

అందువల్ల పునరావృత సంబంధం అవుతుంది:

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

అదే సబ్‌ప్రోబ్లమ్ యొక్క పున omp సంయోగాన్ని అధిగమించడానికి మళ్లీ మళ్లీ మనం కంఠస్థ పట్టికను ఉపయోగిస్తాము. ఇది ఒక * 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) ఎందుకంటే మేము బహుభుజి యొక్క త్రిభుజానికి కనీస స్కోరు ఇచ్చే 3 వేర్వేరు i, j, k విలువలకు విలువ శ్రేణిని దాటుతున్నాము. ఇక్కడ n విలువ శ్రేణి యొక్క పొడవు.

స్థల సంక్లిష్టత

పై కోడ్ యొక్క స్థల సంక్లిష్టత O (n * n) ఎందుకంటే కంఠస్థం కోసం n * n అదనపు స్థలాన్ని ఉపయోగించడం.

ప్రస్తావనలు