סכום מינימלי של כפל n מספרים  


רמת קושי קשה
נשאל לעתים קרובות אקסנצ'ר בלקרוק GE Healthcare JP מורגן פייפאל
מערך תכנות דינמי

הבעיה "סכום מינימלי של הכפלות של n מספרים" קובעת שאתה מקבל n מספרים שלמים ועליך למזער את סכום הכפל של כל המספרים על ידי לקיחת שני אלמנטים הסמוכים בו זמנית ולהחזיר את סכום המוד 100 שלהם עד שיישאר מספר יחיד.

דוגמה  

סכום מינימלי של כפל n מספריםאורן

10 20 30
1100

הסבר

ראשית, אנו מכפילים 10 ו -20 כדי לקבל 200 ואז מחזירים (10 + 20)% 100 = 30. עכשיו יש לנו [30, 30]. ואז הכפל 30 * 30 = 900. לכן התשובה היא 900 + 200 = 1100.

אם היינו מכפילים תחילה 20 ו 30. היינו מקבלים (20 * 30) + (10 * 50) = 1100. כך בשני הכיוונים היינו מקבלים את אותה תוצאה.

גישה  

הבעיה מבקשת מאיתנו למצוא את הסכום המינימלי שניתן למצוא כך שתמשיך להכפיל את המספרים בזוגות ואז לבצע את התוספת שלהם. גישה נאיבית לפתרון הבעיה היא שימוש רקורסיה. צור את כל התמורות ואז שקול שתמורות אלה מסמנות את המדדים שיש להכפיל אותם בזוגות. אך גישה זו גוזלת זמן מכיוון שלדור התמורות יש מורכבות זמן עובדתית.

במקום גישה גוזלת זמן זו, עלינו לחשוב על כל פתרון אחר שמסוגל לחשב את התוצאה במגבלת הזמן. עַכשָׁיו תכנות דינמי בא לעזרתנו. הבעיה היא וריאציה קלה בהשוואה לבעיית הכפל הסטנדרטית של שרשרת המטריצה. כאן בבעיה זו נחשב תחילה את התשובה עבור 2 אלמנטים, ואז 3 אלמנטים וכן הלאה. לכן אנו שומרים על שני משתנים לאחסון המדדים בפונקציה רקורסיבית המציינת את גבול הרצף. לאחר מכן חילקנו את הרצף לשני חלקים. ואז פתר את שתי בעיות המשנה הללו. תהליך זה ממשיך עד שנכנס לתיק הבסיס. כאן המקרה הבסיסי הוא כאשר שני המדדים זהים. ואז כשחשבנו את התשובה עבור תת-בעיות אלה אנו משלבים תשובות כדי לקבל את התוצאה לבעיה הראשונית.

ראה גם
תוכנית לבעיית גשר ולפיד

קופונים  

קוד 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

קוד Java כדי למצוא סכום מינימלי של הכפלות של 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), מכיוון שיצרנו טבלת DP דו-ממדית. לפיכך מורכבות החלל היא גם פולינומית.