Минимизация затрат на сокращение массива до одного элемента путем замены K последовательных элементов их суммой

Опубликовано: 4 Января, 2022

Для массива arr [] размера N и целого числа K задача состоит в том, чтобы найти минимальную стоимость, необходимую для уменьшения данного массива до одного элемента, где стоимость замены K последовательных элементов массива их суммой равна сумме K последовательных элементов. Если невозможно сократить данный массив до одного элемента, выведите -1 .

Примеры:

Input: arr[] = {3, 5, 1, 2, 6}, K = 3
Output: 25
Explanation:
Replacing {arr[1], arr[2], arr[3]} modifies arr[] = {3, 8, 6}. Cost = 8
Replacing {arr[0], arr[1], arr[2]} modifies arr[] = {17}. Cost = 17.
Therefore, the total cost to merge all the array elements into one = 8 + 17 = 25
Input: arr[] = {3, 2, 4, 1}, K = 3
Output: -1
Merging any K (=3) consecutive array elements left 2 elements in the array.
Therefore, the required output is -1.

Подход: проблему можно решить с помощью динамического программирования. Ниже приводится рекуррентное соотношение:

Since the size of the array reduces by (K – 1) after every replacement operation,
dp[i][j] = min(dp[i][x], dp[x+1][j]), X = i + integer * (K – 1)
where, dp[i][j] stores the minimum cost to merge maximum number of array elements in the interval [i, j] with the left most element arr[i] always involved in merge if possible

Выполните следующие действия, чтобы решить проблему:

Если (N - 1)% (K - 1)! = 0, то выведите -1 .
Инициализируйте массив, скажем, prefixSum [], чтобы сохранить сумму префиксов данного массива.
Инициализируйте 2D-массив, скажем, dp [] [] , где dp [i] [j] хранит минимальную стоимость для объединения максимального количества элементов массива в интервале [i, j] .
Заполните таблицу DP, используя вышеупомянутую взаимосвязь между состояниями DP.
Наконец, выведите значение dp [0] [N - 1] .

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to implement
 // the above approach
 #include<bits/stdc++.h>
 using namespace std;
 // Function to find the minimum cost
 // to reduce given array to a single
 // element by replacing consecutive
 // K array elements
 int minimumCostToMergeK( int arr[], int K, int N)
 {
    // If (N - 1) is not
    // multiple of (K - 1)
    if ((N - 1) % (K - 1) != 0)
    {
        return -1;
    }
    
    // Store prefix sum of the array
    int prefixSum[N + 1] = {0}; 
    // Iterate over the range [1, N]
    for ( int i = 1; i < (N + 1); i++)
    {
        
        // Update prefixSum[i]
        prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
    }
    // dp[i][j]: Store minimum cost to
    // merge array elements interval [i, j]
    int dp[N][N];
    memset (dp, 0, sizeof (dp)); 
    // L: Stores length of interval [i, j]
    for ( int L = K; L < (N + 1); L++)
    {
        
        // Iterate over each interval
        // [i, j] of length L in in [0, N]
        for ( int i = 0; i < (N - L + 1); i++)
        {
            
            // Stores index of last element
            // of the interval [i, j]
            int j = i + L - 1; 
            // If L is greater than K
            if (L > K)
            {
                int temp = INT_MAX;
                for ( int x = i; x < j; x += K - 1)
                {
                    temp = min(temp, dp[i][x] +
                                     dp[x + 1][j]);
                }
                
                // Update dp[i][j]
                dp[i][j] = temp;
            }
            // If (L - 1) is multiple of (K - 1)
            if ((L - 1) % (K - 1) == 0)
            {
                
                // Update dp[i][j]
                dp[i][j] += (prefixSum[j + 1] -
                             prefixSum[i]);
            }
        }
    }
    
    // Return dp[0][N - 1]
    return dp[0][N - 1];
 }
 // Driver Code
 int main()
 {
    int arr[] = { 3, 5, 1, 2, 6 };
    int K = 3;
    
      // Stores length of arr
      int N = sizeof (arr) / sizeof (arr[0]);
      
    cout << minimumCostToMergeK(arr, K, N);
 }
 // This code is contributed by rag2127

Джава

 // Java program to implement
 // the above approach
 import java.util.*;
 class GFG
 {
  // Function to find the minimum cost
  // to reduce given array to a single
  // element by replacing consecutive
  // K array elements
  static int minimumCostToMergeK( int arr[], int K, int N)
  {
    // If (N - 1) is not
    // multiple of (K - 1)
    if ((N - 1 ) % (K - 1 ) != 0 )
    {
      return - 1 ;
    }
    // Store prefix sum of the array
    int []prefixSum = new int [N + 1 ]; 
    // Iterate over the range [1, N]
    for ( int i = 1 ; i < (N + 1 ); i++)
    {
      // Update prefixSum[i]
      prefixSum[i] = (prefixSum[i - 1 ] + arr[i - 1 ]); 
    }
    // dp[i][j]: Store minimum cost to
    // merge array elements interval [i, j]
    int [][]dp = new int [N][N]; 
    // L: Stores length of interval [i, j]
    for ( int L = K; L < (N + 1 ); L++)
    {
      // Iterate over each interval
      // [i, j] of length L in in [0, N]
      for ( int i = 0 ; i < (N - L + 1 ); i++)
      {
        // Stores index of last element
        // of the interval [i, j]
        int j = i + L - 1 ; 
        // If L is greater than K
        if (L > K)
        {
          int temp = Integer.MAX_VALUE;
          for ( int x = i; x < j; x += K - 1 )
          {
            temp = Math.min(temp, dp[i][x] +
                            dp[x + 1 ][j]);
          }
          // Update dp[i][j]
          dp[i][j] = temp;
        }
        // If (L - 1) is multiple of (K - 1)
        if ((L - 1 ) % (K - 1 ) == 0 )
        {
          // Update dp[i][j]
          dp[i][j] += (prefixSum[j + 1 ] -
                       prefixSum[i]);
        }
      }
    }
    // Return dp[0][N - 1]
    return dp[ 0 ][N - 1 ];
  }
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 3 , 5 , 1 , 2 , 6 };
    int K = 3 ; 
    // Stores length of arr
    int N = arr.length;
    System.out.print(minimumCostToMergeK(arr, K, N));
  }
 }
 // This code is contributed by shikhasingrajput

Python3

 # Python3 program to implement
 # the above approach
 # Function to find the minimum cost
 # to reduce given array to a single
 # element by replacing consecutive
 # K array elements
 def minimumCostToMergeK(arr, K):
    
    
    # Stores length of arr
    N = len (arr) 
    # If (N - 1) is not
    # multiple of (K - 1)
    if (N - 1 ) % (K - 1 ) ! = 0 :
        return - 1
    
    # Store prefix sum of the array
    prefixSum = [ 0 ] * (N + 1 ) 
    # Iterate over the range [1, N]
    for i in range ( 1 , N + 1 ): 
        # Update prefixSum[i]
        prefixSum[i] = (prefixSum[i - 1 ]
                         + arr[i - 1 ]) 
    # dp[i][j]: Store minimum cost to
    # merge array elements interval [i, j]
    dp = [[ 0 ] * N for _ in range (N)] 
    # L: Stores length of interval [i, j]
    for L in range (K, N + 1 ): 
        # Iterate over each interval
        # [i, j] of length L in in [0, N]
        for i in range (N - L + 1 ): 
            # Stores index of last element
            # of the interval [i, j]
            j = i + L - 1 
            # If L is greater than K
            if L > K: 
                # Update dp[i][j]
                dp[i][j] = (
                     min ([dp[i][x] + dp[x + 1 ][j]
                     for x in range (i, j, K - 1 )]))
             
            # If (L - 1) is multiple of (K - 1)
            if (L - 1 ) % (K - 1 ) = = 0 : 
                # Update dp[i][j]
                dp[i][j] + = (prefixSum[j + 1 ]
                              - prefixSum[i]) 
    # Return dp[0][N - 1]
    return dp[ 0 ][N - 1 ]
 if __name__ = = "__main__" :
    arr = [ 3 , 5 , 1 , 2 , 6 ]
    K = 3
    print (minimumCostToMergeK(arr, K)) 

C #

 // C# program to implement
 // the above approach
 using System;
 class GFG
 {
  // Function to find the minimum cost
  // to reduce given array to a single
  // element by replacing consecutive
  // K array elements
  static int minimumCostToMergeK( int []arr, int K, int N)
  {
    // If (N - 1) is not
    // multiple of (K - 1)
    if ((N - 1) % (K - 1) != 0)
    {
      return -1;
    }
    // Store prefix sum of the array
    int []prefixSum = new int [N + 1]; 
    // Iterate over the range [1, N]
    for ( int i = 1; i < (N + 1); i++)
    {
      // Update prefixSum[i]
      prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
    }
    // dp[i,j]: Store minimum cost to
    // merge array elements interval [i, j]
    int [,]dp = new int [N,N]; 
    // L: Stores length of interval [i, j]
    for ( int L = K; L < (N + 1); L++)
    {
      // Iterate over each interval
      // [i, j] of length L in in [0, N]
      for ( int i = 0; i < (N - L + 1); i++)
      {
        // Stores index of last element
        // of the interval [i, j]
        int j = i + L - 1; 
        // If L is greater than K
        if (L > K)
        {
          int temp = int .MaxValue;
          for ( int x = i; x < j; x += K - 1)
          {
            temp = Math.Min(temp, dp[i, x] +
                            dp[x + 1, j]);
          }
          // Update dp[i,j]
          dp[i, j] = temp;
        }
        // If (L - 1) is multiple of (K - 1)
        if ((L - 1) % (K - 1) == 0)
        {
          // Update dp[i,j]
          dp[i, j] += (prefixSum[j + 1] -
                       prefixSum[i]);
        }
      }
    }
    // Return dp[0,N - 1]
    return dp[0, N - 1];
  }
  // Driver Code
  public static void Main(String[] args)
  {
    int []arr = { 3, 5, 1, 2, 6 };
    int K = 3; 
    // Stores length of arr
    int N = arr.Length;
    Console.Write(minimumCostToMergeK(arr, K, N));
  }
 }
 // This code is contributed by 29AjayKumar

Javascript

 <script>
 // javascript program to implement
 // the above approach
    // Function to find the minimum cost
    // to reduce given array to a single
    // element by replacing consecutive
    // K array elements
    function minimumCostToMergeK(arr , K , N)
    {
        // If (N - 1) is not
        // multiple of (K - 1)
        if ((N - 1) % (K - 1) != 0) {
            return -1;
        }
        // Store prefix sum of the array
        var prefixSum = Array(N + 1).fill(0); 
        // Iterate over the range [1, N]
        for (i = 1; i < (N + 1); i++) { 
            // Update prefixSum[i]
            prefixSum[i] = (prefixSum[i - 1] + arr[i - 1]);
        }
        // dp[i][j]: Store minimum cost to
        // merge array elements interval [i, j]
        var dp = Array(N);
        for ( i = 0; i<N;i++)
        dp[i] = Array(N).fill(0);
        // L: Stores length of interval [i, j]
        for (L = K; L < (N + 1); L++) { 
            // Iterate over each interval
            // [i, j] of length L in in [0, N]
            for (i = 0; i < (N - L + 1); i++) { 
                // Stores index of last element
                // of the interval [i, j]
                var j = i + L - 1; 
                // If L is greater than K
                if (L > K) {
                    var temp = Number.MAX_VALUE;
                    for (x = i; x < j; x += K - 1) {
                        temp = Math.min(temp, dp[i][x] + dp[x + 1][j]);
                    }
                    // Update dp[i][j]
                    dp[i][j] = temp;
                }
                // If (L - 1) is multiple of (K - 1)
                if ((L - 1) % (K - 1) == 0) { 
                    // Update dp[i][j]
                    dp[i][j] += (prefixSum[j + 1] - prefixSum[i]);
                }
            }
        }
        // Return dp[0][N - 1]
        return dp[0][N - 1];
    }
    // Driver Code
    
        var arr = [ 3, 5, 1, 2, 6 ];
        var K = 3; 
        // Stores length of arr
        var N = arr.length;
        document.write(minimumCostToMergeK(arr, K, N));
 // This code is contributed by todaysgaurav
 </script>

Выход:

Сложность времени: O (N ² * K)
Вспомогательное пространство: O (N ² )

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Собеседования

Минимизация затрат на сокращение массива до одного элемента путем замены K последовательных элементов их суммой

C ++

Джава

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ