Costo mínimo de reducir Array al fusionar cualquier elemento adyacente repetidamente

Dada una array arr[] de N números. Podemos fusionar dos números adyacentes en uno y el costo de fusionar los dos números es igual a la suma de los dos valores. La tarea es encontrar el costo mínimo total de fusionar todos los números.
Ejemplos: 
 

Entrada: arr[] = { 6, 4, 4, 6 } 
Salida: 40 
Explicación: 
La siguiente es la forma óptima de combinar números para obtener el costo mínimo total de la combinación de números: 
1. Combinar (6, 4), luego array se convierte en, arr[] = {10, 4, 6} y costo = 10 
2. Combinar (4, 6), luego la array se convierte en, arr[] = {10, 10} y costo = 10 
3. Combinar (10, 10 ), entonces la array se convierte en arr[] = {20} y costo = 20 
Por lo tanto, el costo total es 10 + 10 + 20 = 40.
Entrada: arr[] = { 3, 2, 4, 1 } 
Salida: 20 
Explicación: 
La siguiente es la forma óptima de combinar números para obtener el costo mínimo total de la combinación de números: 
1. Combinar (3, 2), luego la array se convierte en arr[] = {5, 4, 1} y costo = 5 
2. Combinar (4, 1), luego la array se convierte en arr[] = {5, 5} y costo = 5 
3. Combinar (5, 5), luego la array se convierte en arr[] = {10} y costo = 10 
Por lo tanto, el costo total es 5 + 5 + 10 = 20.

Planteamiento: El problema se puede resolver usando Programación Dinámica . A continuación se muestran los pasos: 
 

1. La idea es fusionar 2 números consecutivos en cada posible índice i y luego resolver de forma recursiva las partes izquierda y derecha del índice i .
2. Agregue el resultado de fusionar dos números en los pasos anteriores y almacene el mínimo de ellos.
3. Dado que hay muchos subproblemas que se repiten, usamos la memorización para almacenar los valores en una array NxN .
4. La relación de recurrencia para el enunciado del problema anterior se da como: 
    

dp[i][j] = min(dp[i][j], (suma[i][j] + dp[i][k] + dp[k + 1][j])), para cada ( yo ≤ k lt; j) 

      5. Ahora dp[1][N] dará el costo total mínimo de fusionar todos los números.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the total minimum
// cost of merging two consecutive numbers
int mergeTwoNumbers(vector<int>& numbers)
{
    int len, i, j, k;
 
    // Find the size of numbers[]
    int n = numbers.size();
 
    // If array is empty, return 0
    if (numbers.size() == 0) {
        return 0;
    }
 
    // To store the prefix Sum of
    // numbers array numbers[]
    vector<int> prefixSum(n + 1, 0);
 
    // Traverse numbers[] to find the
    // prefix sum
    for (int i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1]
                       + numbers[i - 1];
    }
 
    // dp table to memoised the value
    vector<vector<int> > dp(
        n + 1,
        vector<int>(n + 1));
 
    // For single numbers cost is zero
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
 
    // Iterate for length >= 1
    for (len = 2; len <= n; len++) {
 
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
 
            // Find sum in range [i..j]
            int sum = prefixSum[j]
                      - prefixSum[i - 1];
 
            // Initialise dp[i][j] to INT_MAX
            dp[i][j] = INT_MAX;
 
            // Iterate for all possible
            // K to find the minimum cost
            for (k = i; k < j; k++) {
 
                // Update the minimum sum
                dp[i][j]
                    = min(dp[i][j],
                          dp[i][k]
                              + dp[k + 1][j]
                              + sum);
            }
        }
    }
 
    // Return the final minimum cost
    return dp[1][n];
}
 
// Driver Code
int main()
{
    // Given set of numbers
    vector<int> arr1 = { 6, 4, 4, 6 };
 
    // Function Call
    cout << mergeTwoNumbers(arr1)
         << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the total minimum
// cost of merging two consecutive numbers
static int mergeTwoNumbers(int []numbers)
{
    int len, i, j, k;
 
    // Find the size of numbers[]
    int n = numbers.length;
 
    // If array is empty, return 0
    if (numbers.length == 0)
    {
        return 0;
    }
 
    // To store the prefix Sum of
    // numbers array numbers[]
    int []prefixSum = new int[n + 1];
 
    // Traverse numbers[] to find the
    // prefix sum
    for (i = 1; i <= n; i++)
    {
        prefixSum[i] = prefixSum[i - 1] +
                         numbers[i - 1];
    }
 
    // dp table to memoised the value
    int [][]dp = new int[n + 1][n + 1];
 
    // Iterate for length >= 1
    for (len = 2; len <= n; len++)
    {
 
        for (i = 1; i <= n - len + 1; i++)
        {
            j = i + len - 1;
 
            // Find sum in range [i..j]
            int sum = prefixSum[j] -
                      prefixSum[i - 1];
 
            // Initialise dp[i][j] to Integer.MAX_VALUE
            dp[i][j] = Integer.MAX_VALUE;
 
            // Iterate for all possible
            // K to find the minimum cost
            for (k = i; k < j; k++)
            {
 
                // Update the minimum sum
                dp[i][j] = Math.min(dp[i][j],
                                    dp[i][k] +
                                    dp[k + 1][j] +
                                    sum);
            }
        }
    }
 
    // Return the final minimum cost
    return dp[1][n];
}
 
// Driver Code
public static void main(String[] args)
{
    // Given set of numbers
    int []arr1 = { 6, 4, 4, 6 };
 
    // Function Call
    System.out.print(mergeTwoNumbers(arr1) + "\n");
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program for the above approach
import sys
 
# Function to find the total minimum
# cost of merging two consecutive numbers
def mergeTwoNumbers(numbers):
 
    # Find the size of numbers[]
    n = len(numbers)
 
    # If array is empty, return 0
    if (len(numbers) == 0):
        return 0
     
    # To store the prefix Sum of
    # numbers array numbers[]
    prefixSum = [0] * (n + 1)
 
    # Traverse numbers[] to find the
    # prefix sum
    for i in range(1, n + 1):
        prefixSum[i] = (prefixSum[i - 1] +
                          numbers[i - 1])
     
    # dp table to memoised the value
    dp = [[0 for i in range(n + 1)]
             for j in range(n + 1)]
 
    # For single numbers cost is zero
    for i in range(1, n + 1):
        dp[i][i] = 0
     
    # Iterate for length >= 1
    for p in range(2, n + 1):
        for i in range(1, n - p + 2):
            j = i + p - 1
 
            # Find sum in range [i..j]
            sum = prefixSum[j] - prefixSum[i - 1]
 
            # Initialise dp[i][j] to _MAX
            dp[i][j] = sys.maxsize
 
            # Iterate for all possible
            # K to find the minimum cost
            for k in range(i, j):
 
                # Update the minimum sum
                dp[i][j] = min(dp[i][j],
                              (dp[i][k] +
                               dp[k + 1][j] + sum))
             
    # Return the final minimum cost
    return dp[1][n]
 
# Driver Code
 
# Given set of numbers
arr1 = [ 6, 4, 4, 6 ]
 
# Function call
print(mergeTwoNumbers(arr1))
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
class GFG{
 
// Function to find the total minimum
// cost of merging two consecutive numbers
static int mergeTwoNumbers(int []numbers)
{
    int len, i, j, k;
 
    // Find the size of numbers[]
    int n = numbers.Length;
 
    // If array is empty, return 0
    if (numbers.Length == 0)
    {
        return 0;
    }
 
    // To store the prefix Sum of
    // numbers array numbers[]
    int []prefixSum = new int[n + 1];
 
    // Traverse numbers[] to find the
    // prefix sum
    for (i = 1; i <= n; i++)
    {
        prefixSum[i] = prefixSum[i - 1] +
                         numbers[i - 1];
    }
 
    // dp table to memoised the value
    int [,]dp = new int[n + 1, n + 1];
 
    // Iterate for length >= 1
    for (len = 2; len <= n; len++)
    {
 
        for (i = 1; i <= n - len + 1; i++)
        {
            j = i + len - 1;
 
            // Find sum in range [i..j]
            int sum = prefixSum[j] -
                      prefixSum[i - 1];
 
            // Initialise dp[i,j] to int.MaxValue
            dp[i,j] = int.MaxValue;
 
            // Iterate for all possible
            // K to find the minimum cost
            for (k = i; k < j; k++)
            {
 
                // Update the minimum sum
                dp[i, j] = Math.Min(dp[i, j],
                                    dp[i, k] +
                                    dp[k + 1, j] +
                                    sum);
            }
        }
    }
 
    // Return the readonly minimum cost
    return dp[1, n];
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given set of numbers
    int []arr1 = { 6, 4, 4, 6 };
 
    // Function Call
    Console.Write(mergeTwoNumbers(arr1) + "\n");
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// JavaScript program for the above approach
 
// Function to find the total minimum
// cost of merging two consecutive numbers
function mergeTwoNumbers(numbers)
{
    var len, i, j, k;
 
    // Find the size of numbers[]
    var n = numbers.length;
 
    // If array is empty, return 0
    if (numbers.length == 0) {
        return 0;
    }
 
    // To store the prefix Sum of
    // numbers array numbers[]
    var prefixSum = Array(n+1).fill(0);
 
    // Traverse numbers[] to find the
    // prefix sum
    for (var i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1]
                       + numbers[i - 1];
    }
 
    // dp table to memoised the value
    var dp = Array.from(Array(n+1), ()=>Array(n+1));
 
    // For single numbers cost is zero
    for (var i = 1; i <= n; i++) {
        dp[i][i] = 0;
    }
 
    // Iterate for length >= 1
    for (len = 2; len <= n; len++) {
 
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
 
            // Find sum in range [i..j]
            var sum = prefixSum[j]
                      - prefixSum[i - 1];
 
            // Initialise dp[i][j] to INT_MAX
            dp[i][j] = 1000000000;
 
            // Iterate for all possible
            // K to find the minimum cost
            for (k = i; k < j; k++) {
 
                // Update the minimum sum
                dp[i][j]
                    = Math.min(dp[i][j],
                          dp[i][k]
                              + dp[k + 1][j]
                              + sum);
            }
        }
    }
 
    // Return the final minimum cost
    return dp[1][n];
}
 
// Driver Code
 
// Given set of numbers
var arr1 = [6, 4, 4, 6];
 
// Function Call
document.write( mergeTwoNumbers(arr1))
 
 
</script>

40

Complejidad Temporal: O(N ³ )  
Complejidad Espacial Auxiliar: O(N ² )