Минимизация затрат на сокращение массива до одного элемента путем замены 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>
Выход:
 25

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

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

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