n个数字的最小乘法和


难度级别
经常问 Accenture 贝莱德 GE医疗集团 JP摩根 贝宝
排列 动态编程

问题“ 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。因此,两种方式我们都将得到相同的结果。

途径

问题要求我们找到可以找到的最小和,以便您继续将数字成对相乘,然后再进行相加。 解决该问题的幼稚方法是使用 递归。 生成所有排列,然后考虑这些排列表示应该成对相乘的索引。 但是这种方法很耗时,因为排列的产生具有阶乘时间复杂性。

代替这种费时的方法,我们应该考虑能够在时限内计算结果的任何其他解决方案。 现在 动态编程 来帮助我们。 问题是与标准矩阵链乘法问题略有不同。 在此问题中,我们首先计算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), 因为我们已经创建了2D DP表。 因此,空间复杂度也是多项式。