Dados n enteros. La tarea es minimizar la suma de la multiplicación de todos los números tomando dos números adyacentes a la vez y devolviendo su suma % 100 hasta que quede un número.
Ejemplos:
Input : 40 60 20 Output : 2400 Explanation: There are two possible cases: 1st possibility: Take 40 and 60, so multiplication=2400 and put back (60+40) % 100 = 0, making it 0, 20. Multiplying 0 and 20 we get 0 so multiplication = 2400+0 = 2400. Put back (0+20)%100 = 20. 2nd possibility: take 60 and 20, so 60*20 = 1200, put back (60+20)%100 = 80, making it [40, 80] multiply 40*80 to get 3200, so multiplication sum = 1200+3200 = 4400. Put back (40+80)%100 = 20 Input : 5 6 Output : 30 Explanation: Only possibility is 5*6=30
Enfoque: El problema es una variación de la array en string Multiplicación Programación dinámica
La idea es dividir N números en todos los valores posibles de k. Resuelva recursivamente para partes más pequeñas y agregue la multiplicación y almacene el mínimo de ellas. Como lo estamos dividiendo en k partes, para cada DP i,j tendremos k particiones i<=k<j , almacene el mínimo de ellas. Entonces obtenemos la fórmula similar a la Programación dinámica de multiplicación de string matricial .
DP i,j = min(DP i,j , (DP i,k +DP k+1,j +(cumulative_sum i,k *cumulative_sum k+1,j ) ) )
para cada i<=k<j.
Dado que muchos subproblemas se repetirán, usamos la memorización para almacenar los valores en una array nXn.
A continuación se muestra la ilustración del enfoque anterior:
C++
// CPP program to find the
// minimum sum of multiplication
// of n numbers
#include <bits/stdc++.h>
using namespace std;
// Used in recursive
// memoized solution
long long dp[1000][1000];
// function to calculate the cumulative
// sum from a[i] to a[j]
long long sum(int a[], int i, int j)
{
long long ans = 0;
for (int m = i; m <= j; m++)
ans = (ans + a[m]) % 100;
return ans;
}
long long solve(int a[], int i, int j)
{
// base case
if (i == j)
return 0;
// memoization, if the partition
// has been called before then
// return the stored value
if (dp[i][j] != -1)
return dp[i][j];
// store a max value
dp[i][j] = INT_MAX;
// we break them into k partitions
for (int k = i; k < j; k++)
{
// store the min of the
// formula thus obtained
dp[i][j] = min(dp[i][j], (solve(a, i, k) +
solve(a, k + 1, j) +
(sum(a, i, k) * sum(a, k + 1, j))));
}
// return the minimum
return dp[i][j];
}
void initialize(int n)
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
dp[i][j] = -1;
}
// Driver code
int main() {
int a[] = {40, 60, 20};
int n = sizeof(a) / sizeof(a[0]);
initialize(n);
cout << solve(a, 0, n - 1) << endl;
return 0;
}
Java
// Java program to find the
// minimum sum of multiplication
// of n numbers
import java.io.*;
import java.math.*;
class GFG
{
// Used in recursive
// memoized solution
static long dp[][] = new long[1000][1000];
// function to calculate the
// cumulative sum from a[i] to a[j]
static long sum(int a[], int i, int j)
{
long ans = 0;
for (int m = i; m <= j; m++)
ans = (ans + a[m]) % 100;
return ans;
}
static long solve(int a[], int i, int j)
{
// base case
if (i == j)
return 0;
// memoization, if the partition
// has been called before then
// return the stored value
if (dp[i][j] != -1)
return dp[i][j];
// store a max value
dp[i][j] = 100000000;
// we break them into k partitions
for (int k = i; k < j; k++)
{
// store the min of the
// formula thus obtained
dp[i][j] = Math.min(dp[i][j], (solve(a, i, k) +
solve(a, k + 1, j) +
(sum(a, i, k) * sum(a, k + 1,j))));
}
// return the minimum
return dp[i][j];
}
static void initialize(int n)
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
dp[i][j] = -1;
}
// Driver code
public static void main(String args[])
{
int a[] = {40, 60, 20};
int n = a.length;
initialize(n);
System.out.println(solve(a, 0, n - 1));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python3 program to find the # minimum sum of multiplication # of n numbers import numpy as np import sys # Used in recursive # memoized solution dp = np.zeros((1000,1000)) # function to calculate the cumulative # sum from a[i] to a[j] def sum(a, i, j) : ans = 0 for m in range(i, j + 1) : ans = (ans + a[m]) % 100 return ans def solve(a, i, j) : # base case if (i == j) : return 0 # memoization, if the partition # has been called before then # return the stored value if (dp[i][j] != -1) : return dp[i][j] # store a max value dp[i][j] = sys.maxsize # we break them into k partitions for k in range(i, j) : # store the min of the # formula thus obtained dp[i][j] = min(dp[i][j], (solve(a, i, k) + solve(a, k + 1, j) + (sum(a, i, k) * sum(a, k + 1, j)))) # return the minimum return dp[i][j] def initialize(n) : for i in range(n + 1) : for j in range(n + 1) : dp[i][j] = -1 #Driver code if __name__ == "__main__" : a = [40, 60, 20] n = len(a) initialize(n) print(int(solve(a, 0, n - 1))) # This code is contributed by Ryuga
C#
// C# program to find the
// minimum sum of multiplication
// of n numbers
using System;
class GFG
{
// Used in recursive
// memoized solution
static long [,]dp = new long[1000, 1000];
// Function to calculate the cumulative
// sum from a[i] to a[j]
static long sum(int []a, int i, int j)
{
long ans = 0;
for (int m = i; m <= j; m++)
ans = (ans + a[m]) % 100;
return ans;
}
static long solve(int []a, int i, int j)
{
// base case
if (i == j)
return 0;
// memoization, if the partition
// has been called before then
// return the stored value
if (dp[i, j] != -1)
return dp[i, j];
// store a max value
dp[i, j] = 100000000;
// we break them into k partitions
for (int k = i; k < j; k++)
{
// store the min of the
// formula thus obtained
dp[i, j] = Math.Min(dp[i, j], (solve(a, i, k) +
solve(a, k + 1, j) +
(sum(a, i, k) * sum(a, k + 1, j))));
}
// return the minimum
return dp[i, j];
}
static void initialize(int n)
{
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
dp[i, j] = -1;
}
// Driver code
public static void Main()
{
int []a = {40, 60, 20};
int n = a.Length;
initialize(n);
Console.WriteLine(solve(a, 0, n - 1));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find the
// minimum sum of multiplication
// of n numbers
// Used in recursive
// memoized solution
$dp = array(array());
// function to calculate the
// cumulative sum from a[i] to a[j]
function sum( $a, $i, $j)
{
$ans = 0;
for ( $m = $i; $m <= $j; $m++)
$ans = ($ans + $a[$m]) % 100;
return $ans;
}
function solve( $a, $i, $j)
{
global $dp;
// base case
if ($i == $j)
return 0;
// memoization, if the partition
// has been called before then
// return the stored value
if ($dp[$i][$j] != -1)
return $dp[$i][$j];
// store a max value
$dp[$i][$j] = PHP_INT_MAX;
// we break them into
// k partitions
for ( $k = $i; $k < $j; $k++)
{
// store the min of the
// formula thus obtained
$dp[$i][$j] = min($dp[$i][$j],
(solve($a, $i, $k) +
solve($a, $k + 1, $j) +
(sum($a, $i, $k) *
sum($a, $k + 1, $j))));
}
// return the minimum
return $dp[$i][$j];
}
function initialize( $n)
{
global $dp;
for ( $i = 0; $i <= $n; $i++)
for ( $j = 0; $j <= $n; $j++)
$dp[$i][$j] = -1;
}
// Driver code
$a = array(40, 60, 20);
$n = count($a);
initialize($n);
echo solve($a, 0, $n - 1) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find the
// minimum sum of multiplication
// of n numbers
// Used in recursive
// memoized solution
var dp = Array.from(Array(1000), ()=>Array(1000));
// function to calculate the cumulative
// sum from a[i] to a[j]
function sum( a, i, j)
{
var ans = 0;
for (var m = i; m <= j; m++)
ans = (ans + a[m]) % 100;
return ans;
}
function solve( a, i, j)
{
// base case
if (i == j)
return 0;
// memoization, if the partition
// has been called before then
// return the stored value
if (dp[i][j] != -1)
return dp[i][j];
// store a max value
dp[i][j] = 1000000000;
// we break them into k partitions
for (var k = i; k < j; k++)
{
// store the min of the
// formula thus obtained
dp[i][j] = Math.min(dp[i][j], (solve(a, i, k) +
solve(a, k + 1, j) +
(sum(a, i, k) * sum(a, k + 1, j))));
}
// return the minimum
return dp[i][j];
}
function initialize(n)
{
for (var i = 0; i <= n; i++)
for (var j = 0; j <= n; j++)
dp[i][j] = -1;
}
// Driver code
var a = [40, 60, 20];
var n = a.length;
initialize(n);
document.write( solve(a, 0, n - 1));
</script>
Producción:
2400
Complejidad de tiempo: O(n^3)
Espacio auxiliar: O(n^2)