ពិន្ទុត្រីកោណអប្បបរមានៃដំណោះស្រាយពហុបច្ចេកទេស Leetcode


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Uber
ការសរសេរកម្មវិធីឌីណាមិក

សេចក្តីថ្លែងការណ៍បញ្ហា

នៅក្នុងបញ្ហា” ពិន្ទុអប្បបរមា ត្រីកោណ of ពហុកោណយើងត្រូវបានគេផ្តល់តម្លៃអារេមួយដែលធាតុនីមួយៗនៅក្នុងអារេតំណាងឱ្យតម្លៃនៃពហុកោណរាងអក្សរ N នៅពេលដាក់ស្លាកក្នុងទ្រនិចនាឡិកា។

ភារកិច្ចរបស់យើងគឺកាត់ត្រីកោណពហុកោណទៅជាត្រីកោណ N-2 ។ ពិន្ទុដើម្បីត្រីកោណត្រីកោណគឺជាផលគុណនៃតម្លៃនៅកំពូលទាំងបីរបស់វា។ ពិន្ទុសរុបដើម្បីត្រីកោណពហុកោណគឺជាផលបូកនៃពិន្ទុនៃត្រីកោណទាំងអស់។

យើងត្រូវរកពិន្ទុអប្បបរមានៃត្រីកោណនៃពហុកោណ។

ឧទាហរណ៍

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

ការពន្យល់:  យើងនឹងទទួលបានពិន្ទុអប្បបរមាសម្រាប់ត្រីកោណនៅពេលយើងដាក់ត្រីកោណតាមវិធីនេះ៖

១ * ១ * ៣ + ១ * ១ * ៤ + ១ * ១ * ៥ + ១ * ១ * ១ = ១៣

វិធីសាស្រ្តសម្រាប់ពិន្ទុត្រីកោណអប្បបរមានៃដំណោះស្រាយពហុកោណឡេឡេលេខកូដ

សូមចងចាំថាយើងត្រូវដាក់ត្រីកោណពហុកោណទៅជាត្រីកោណ N-2 ហើយត្រីកោណមិនគួរជាន់គ្នាទេ។ រាល់គែមនៃពហុកោណអាចជាផ្នែកមួយនៃត្រីកោណភាគច្រើនព្រោះការត្រួតលើគ្នាមិនត្រូវបានអនុញ្ញាតទេ។

ដូច្នេះគ្រប់គែមនៃពហុកោណអាចបង្កើតជាត្រីកោណដែលមានកំពូលបញ្ឈរ N-2 ។ សូមមើលរូបភាពខាងក្រោម។

ពិន្ទុត្រីកោណអប្បបរមានៃដំណោះស្រាយពហុបច្ចេកទេស Leetcode

 

នៅពេលដែលយើងកាត់ត្រីកោណពីពហុកោណយើងនៅសល់ជាមួយពហុកោណតូចជាងថ្មី។ នេះនាំឱ្យយើងឈានដល់ចំណុចមួយដែលយើងអាចបំបែកបញ្ហាទៅជាអនុសញ្ញាណតូចៗ។

ពិន្ទុត្រីកោណអប្បបរមានៃដំណោះស្រាយពហុបច្ចេកទេស Leetcode

 

ដូច្នេះប្រសិនបើយើងចង់បានពិន្ទុអប្បបរមាសម្រាប់ពហុកោណដែលមាន vertex ពី ០-៦ បន្ទាប់មកធាតុរងថ្មីគឺជាពិន្ទុអប្បបរមាសម្រាប់ពហុកោណដែលមាន vertex ពី ០-៣ និង ៣-៦ ។

ដូច្នេះទំនាក់ទំនងហៅខ្លួនឯងបានក្លាយជា:

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) ពីព្រោះយើងកំពុងត្រាប់តាមតំរុយតំរុយសំរាប់តំលៃ ៣ ផ្សេងគ្នាអាយ, ខ, គដែលផ្តល់ពិន្ទុអប្បបរមាសំរាប់ត្រីកោណពហុកោណ។ នៅទីនេះ n គឺជាប្រវែងនៃអារេតម្លៃ។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ O (n * n) ពីព្រោះការប្រើទំហំបន្ថែម n * n សម្រាប់ការទន្ទេញចាំ។

ឯកសារយោង