संख्याको गुणाको न्यूनतम योग


कठिनाई तह हार्ड
बारम्बार सोधिन्छ एक्सेंचर BlackRock जीई हेल्थकेयर जेपी मोर्गन PayPal
एरे डायनामिक प्रोग्रामिंग

समस्या "n संख्या को गुणन को न्यूनतम योग" भन्छ कि तपाइँ एन पूर्णांकहरू र तपाईले सबै संख्याको गुणन को योग न्यूनतम गर्न आवश्यक छ दुईवटा तत्वहरू जुन एक पटकमा सटेको छ र तिनीहरूको संख्या मोड १०० पछाडि एकल संख्या छोड्दा सम्म।

उदाहरणका

संख्याको गुणाको न्यूनतम योग

10 20 30
1100

स्पष्टीकरण

पहिले हामी २०० र १० लाई गुणा पार्छौं तब (१० + २०)% १०० = .०। अब हामीसँग [,०, ]०] छ। त्यसपछि multip० * =० = multip ०० गुणा गर्नुहोस्। यसरी उत्तर 10 ०० + २०० = ११०० हो।

यदि हामी पहिलो २० र 20० गुणा गरेका हुन्छौं। हामीले (२० * )०) + (१० * )०) = ११०० पाएका छौं। यसरी दुबै तरीकाले हामीले समान परिणाम प्राप्त गरेका हुनेछौं।

दृष्टिकोण

समस्याले हामीलाई न्यूनतम योग फेला पार्न सोध्छ जुन यस्तो फेला पार्न सकिन्छ कि तपाईले जोडाहरूमा नम्बरहरू गुणा गर्ने र त्यसपछि तिनीहरूको थप गरिरहनु भएको। समस्या समाधान गर्न भोली दृष्टिकोण प्रयोग गर्दैछ पुनरावृत्ति। सबै आवागमनहरू उत्पन्न गर्नुहोस् र विचार गर्नुहोस् कि यी क्रमवारीहरूले सूचकांकहरूलाई संकेत गर्दछ जुन जोडीमा गुणा गर्नुपर्छ। तर यो दृष्टिकोण समय उपभोक्ता हो किनकि क्रमबद्धताको पुस्तामा तथ्या time्कपूर्ण समय जटिलता हुन्छ।

यस समय-उपभोक्ता दृष्टिकोणको सट्टामा हामीले कुनै अन्य समाधानको बारेमा सोच्नु पर्छ जुन समय सीमा अन्तर्गत परिणाम गणना गर्न सक्षम छ। अब डायनामिक प्रोग्रामिंग हाम्रो सहायता गर्न आउँछ। समस्या मानक मैट्रिक चेन गुणन समस्यामा थोरै भिन्नता हो। यहाँ यो समस्यामा हामी पहिले २ तत्वहरू, त्यसपछि elements तत्वहरू, र यस्तै अन्यका लागि उत्तर गणना गर्छौं। त्यसैले हामी सूचकहरुलाई रिकर्सिभ फंक्शनमा भण्डारण गर्नका लागि दुई चर राख्छौं जुन अनुक्रमको सीमा दर्शाउँछ। त्यसपछि हामी क्रमलाई २ भागमा विभाजित गर्‍यौं। र त्यसपछि यी दुई उप-समस्याहरू समाधान गर्नुहोस्। यस प्रक्रिया हामी चलिरहन्छ जब सम्म हामी बेस केस मा हिर्काउँदैनौं। यहाँ बेस केस हो जब दुबै सूचकहरू एकै हुन्। त्यसो भए हामीले प्रारम्भिक समस्याको नतीजा प्राप्त गर्न यी सबप्रुब्लम्सको लागि उत्तरको हिसाब गर्दा हामी जवाफहरू संयोजन गर्छौं।

कोड

C ++ कोड n संख्याहरूको गुणनको न्यूनतम योग फेला पार्न

#include <bits/stdc++.h>
using namespace std;
int dp[5][5];
int sum(int i, int j, int a[]){
  int ans = 0;
  for (int k=i;k<=j;k++)
    ans=(ans+a[k])%100;
  return ans;
}

int minimumSum(int i, int j, int a[]){
    if(i==j)return 0;
  if (dp[i][j] != INT_MAX)
    return dp[i][j];
    // divide the problem into subproblems
  for(int k=i;k<j;k++)
        dp[i][j] = min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
  return dp[i][j];
}

int main() {
  int a[] = {10, 20, 30};
  int n = sizeof(a) / sizeof(a[0]);
  for(int i=0;i<5;i++){
        for(int j=0;j<5;j++)
            dp[i][j] = INT_MAX;
  }
  cout<<minimumSum(0,n-1,a);
}
1100

जाभा कोड n संख्या को गुणा न्यूनतम योग फेला पार्न

import java.util.*;
class Main{
  static int dp[][] = new int[5][5];
  static int sum(int i, int j, int a[]){
    int ans = 0;
    for (int k=i;k<=j;k++)
      ans=(ans+a[k])%100;
    return ans;
  }

  static int minimumSum(int i, int j, int a[]){
      if(i==j)return 0;
    if (dp[i][j] != Integer.MAX_VALUE)
      return dp[i][j];
      // divide the problem into subproblems
    for(int k=i;k<j;k++)
          dp[i][j] = Math.min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
    return dp[i][j];
  }

  public static void main(String[] args)
  {
    int a[] = {10, 20, 30};
    int n = a.length;
    for(int i=0;i<5;i++){
          for(int j=0;j<5;j++)
              dp[i][j] = Integer.MAX_VALUE;
    }
    int ans = minimumSum(0,n-1,a);
    	System.out.print(ans);
  	}
}
1100

जटिलता विश्लेषण

समय जटिलता

O (N ^ 3), किनभने त्यहाँ N ^ 2 राज्यहरू छन् र परिणाम गणना गर्न हामी प्रत्येकको लागि अनुमानित N राज्यहरूमा निर्भर छौं। यसैले समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (N ^ 2), किनकि हामीले २d DP तालिका सिर्जना गरेका छौं। यसैले अन्तरिक्ष जटिलता पनि बहुपद हो।