બહુકોણ લેટકોડ સોલ્યુશનનું ન્યૂનતમ સ્કોર ત્રિકોણ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ઉબેર
ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા નિવેદન

સમસ્યામાં ”ન્યૂનતમ સ્કોર ત્રિકોણ of બહુકોણ"અમને એક મૂલ્ય એરે આપવામાં આવે છે જ્યાં ઘડિયાળની દિશામાં લેબલ થયેલ હોય ત્યારે એરેમાં દરેક તત્વ એન-બાજુવાળા બહુકોણનું મૂલ્ય રજૂ કરે છે.

અમારું કાર્ય બહુકોણને N-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]

તે જ પેટા પ્રોબ્લેમની પુનomપ્રાપ્તિને દૂર કરવા માટે અને ફરીથી આપણે મેમોરાઇઝેશન ટેબલનો ઉપયોગ કરીશું. આ એક * n એરે હશે જ્યાં 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 જુદા જુદા i, j, k કિંમતો માટે મૂલ્યના એરેને શોધી રહ્યા છીએ જે બહુકોણના ત્રિકોણાકાર માટે ન્યૂનતમ સ્કોર આપે છે. અહીં n એ વેલ્યુ એરેની લંબાઈ છે.

જગ્યાની જટિલતા

ઉપરોક્ત કોડની અવકાશ જટિલતા છે ઓ (એન * એન) કારણ કે યાદ માટે n * n વધારાની જગ્યા નો ઉપયોગ કરવો.

સંદર્ભ