Բազմակողմանի Leetcode լուծույթի նվազագույն միավորի եռանկյունումը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Uber
Դինամիկ ծրագրավորում

Խնդրի հայտարարություն

Խնդիրի մեջ »Նվազագույն միավոր Triangulation 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

Բազմակողմանի Leetcode լուծույթի նվազագույն միավորի եռանկյունացման մոտեցում

Նկատի ունենալով, որ մենք պետք է բազմանկյունը եռանկյունացնենք N-2 եռանկյունու և եռանկյունները չպետք է համընկնեն: Պոլիգոնի յուրաքանչյուր եզր կարող է լինել առավելագույնը մեկ եռանկյունու մաս, քանի որ համընկնումը չի թույլատրվում:

Այսպիսով, բազմանկյունի յուրաքանչյուր եզր կարող է կազմել եռանկյուն `N-2 մնացած գագաթներով: Անդրադարձեք ստորև ներկայացված նկարին:

Բազմակողմանի Leetcode լուծույթի նվազագույն միավորի եռանկյունումը

 

Երբ բազմանկյունից կտրում ենք եռանկյունին, մեզ մնում է նոր ավելի փոքր բազմանկյուն: Սա մեզ հանգեցրեց այն կետի, որ մենք կարող ենք խնդիրը վերածել ավելի փոքր ենթախնդիրների:

Բազմակողմանի Leetcode լուծույթի նվազագույն միավորի եռանկյունումը

 

Այսպիսով, եթե մենք ուզում ենք 0-6 գագաթով բազմանկյունի համար նվազագույն միավոր, ապա նոր ենթածրագիրը նվազագույն միավոր է 0-3-ից և 3-6-ին գագաթով բազմանկյունի համար:

հետևաբար ռեկուրսիվ կապը դառնում է.

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

Նույն ենթախնդրի վերահաշվարկը կրկին ու կրկին հաղթահարելու համար մենք կօգտագործենք անգիր աղյուսակ: Սա կլինի * n զանգված, որտեղ i- ի արժեքը կպահի բազմանկյան նվազագույն միավորի եռանկյունացումը ՝ 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

Java բազայի բազմանկյունի նվազագույն միավորի եռանկյունի համար

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

Բազմակողմանի Leetcode լուծույթի նվազագույն միավորի եռանկյունացման բարդության վերլուծություն

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n * n * n) քանի որ մենք անցնում ենք արժեքի զանգվածը 3 տարբեր i, j, k արժեքների համար, որոնք տալիս են բազմանկյունի եռանկյունացման նվազագույն միավոր: Այստեղ n- ը արժեքի զանգվածի երկարությունն է:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է O (n * n) քանի որ օգտագործելով n * n լրացուցիչ տարածք հիշելու համար:

Սայլակ