Минимална сума от умножения на n числа  


Ниво на трудност Трудно
Често задавани в Accenture BlackRock GE Healthcare JP Morgan PayPal
Array Динамично програмиране

Проблемът „Минимална сума на умноженията на n числа“ гласи, че ви е дадено n числа и трябва да сведете до минимум сумата на умножението на всички числа, като вземете два елемента, които са в съседство едновременно и върнете тяхната сума mod 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. По този начин и по двата начина щяхме да получим един и същ резултат.

Подход  

Проблемът ни изисква да намерим минималната сума, която може да бъде намерена, така че да продължите да умножавате числата по двойки и след това да ги добавяте. Използва се наивен подход за решаване на проблема рекурсия. Генерирайте всички пермутации и след това преценете, че тези пермутации означават индексите, които трябва да се умножат по двойки. Но този подход отнема много време, тъй като генерирането на пермутации има факториална сложност във времето.

Вместо този отнемащ време подход, трябва да помислим за всяко друго решение, което може да изчисли резултата под ограничението във времето. Сега Динамично програмиране идва на помощ. Проблемът е леко отклонение от стандартния проблем за умножение на Matric Chain. Тук в този проблем първо изчисляваме отговора за 2 елемента, след това за 3 елемента и т.н. Така че ние запазваме две променливи за съхраняване на индексите в рекурсивна функция, която обозначава границата на последователността. След това разделихме последователността на 2 части. И след това решете тези два подпроблеми. Този процес продължава, докато не ударим основния случай. Тук основният случай е, когато и двата индекса са еднакви. След това, тъй като сме изчислили отговора за тези подпроблеми, ние комбинираме отговорите, за да получим резултата за първоначалния проблем.

Вижте също
Програма за проблем с мост и факел

код  

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), защото създадохме 2D DP таблица. По този начин сложността на пространството също е многочленна.