Минимален збир на множења на n броеви  


Ниво на тешкотија Тешко
Често прашувано во Accenture Blackrock ГЕ здравство ЈП Морган PayPal
Низа Динамичко програмирање

Проблемот „Минимален збир на множења на 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. Weе добиевме (20 * 30) + (10 * 50) = 1100. Така и на двата начина ќе го добиевме истиот резултат.

Пристап  

Проблемот бара од нас да ја најдеме минималната сума што може да се најде така што ќе продолжите да ги множите броевите во парови, а потоа да го правите нивното собирање. Наивен пристап за решавање на проблемот е користење рекурзија. Генерирајте ги сите пермутации и потоа сметајте дека овие пермутации ги означуваат индексите што треба да се множат во парови. Но, овој пристап одзема многу време, бидејќи генерирањето пермутации има факторска сложеност во времето.

Наместо овој пристап што одзема многу време, треба да размислиме за кое било друго решение што е во состојба да го пресмета резултатот под временското ограничување. Сега Динамичко програмирање ни доаѓа на помош. Проблемот е мала варијација во однос на стандардниот проблем со множење на матричниот синџир. Тука во овој проблем прво го пресметуваме одговорот за 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

Анализа на сложеност  

Временска комплексност

О (N ^ 3), бидејќи постојат N ^ 2 состојби и за да го пресметаме резултатот за секоја од нас зависиме од приближниот N број на состојби. Така, временската сложеност е полином.

Комплексноста на просторот

О (N ^ 2), затоа што креиравме табела со 2Д ДП. Така, вселенската комплексност е исто така полиномна.