Dada una array A[] , la tarea es encontrar el número mínimo de operaciones requeridas en las que se eliminan dos elementos adyacentes de la array y se reemplazan por su suma, de modo que la array se convierta en una array no creciente.
Nota: una array con un solo elemento se considera no creciente.
Ejemplos:
Entrada: A[] = {1, 5, 3, 9, 1}
Salida: 2
Explicación:
Reemplazar {1, 5} por {6} modifica la array a {6, 3, 9, 1}
Reemplazar {6, 3 } por {9} modifica la array a {9, 9, 1}
Entrada: A[] = {0, 1, 2}
Salida: 2
Enfoque: La idea es utilizar Programación Dinámica . Se utiliza una tabla de memorización para almacenar el recuento mínimo de operaciones requeridas para hacer que los subarreglos no aumenten de derecha a izquierda del arreglo dado. Siga los pasos a continuación para resolver el problema:
- Inicialice un arreglo dp[] donde dp[i] almacene el número mínimo de operaciones requeridas para hacer que el subarreglo {A[i], …, A[N]} no sea creciente. Por lo tanto, el objetivo es calcular dp[0].
- Encuentre un subarreglo mínimo {A[i] .. A[j]} tal que sum({A[i] … A[j]}) > val[j+1] , donde, val[j + 1] es el suma combinada obtenida para el subarreglo {A[j + 1], … A[N]} .
- Actualice dp[i] a j – i + dp[j+1] y vals[i] a sum({A[i] … A[j]}) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum operations // to make the array Non-increasing int solve(vector<int>& a) { // Size of the array int n = a.size(); // Dp table initialization vector<int> dp(n + 1, 0), val(n + 1, 0); // dp[i]: Stores minimum number of // operations required to make // subarray {A[i], ..., A[N]} non-increasing for (int i = n - 1; i >= 0; i--) { long long sum = a[i]; int j = i; while (j + 1 < n and sum < val[j + 1]) { // Increment the value of j j++; // Add current value to sum sum += a[j]; } // Update the dp tables dp[i] = (j - i) + dp[j + 1]; val[i] = sum; } // Return the answer return dp[0]; } // Driver code int main() { vector<int> arr = { 1, 5, 3, 9, 1 }; cout << solve(arr); }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find the minimum operations // to make the array Non-increasing static int solve(int []a) { // Size of the array int n = a.length; // Dp table initialization int []dp = new int[n + 1]; int []val = new int[n + 1]; // dp[i]: Stores minimum number of // operations required to make // subarray {A[i], ..., A[N]} non-increasing for (int i = n - 1; i >= 0; i--) { int sum = a[i]; int j = i; while (j + 1 < n && sum < val[j + 1]) { // Increment the value of j j++; // Add current value to sum sum += a[j]; } // Update the dp tables dp[i] = (j - i) + dp[j + 1]; val[i] = sum; } // Return the answer return dp[0]; } // Driver code public static void main(String[] args) { int []arr = { 1, 5, 3, 9, 1 }; System.out.print(solve(arr)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 program to implement # the above approach # Function to find the minimum operations # to make the array Non-increasing def solve(a): # Size of the array n = len(a) # Dp table initialization dp = [0] * (n + 1) val = [0] * (n + 1) # dp[i]: Stores minimum number of # operations required to make # subarray {A[i], ..., A[N]} non-increasing for i in range(n - 1, -1, -1): sum = a[i] j = i while(j + 1 < n and sum < val[j + 1]): # Increment the value of j j += 1 # Add current value to sum sum += a[j] # Update the dp tables dp[i] = (j - i) + dp[j + 1] val[i] = sum # Return the answer return dp[0] # Driver Code arr = [ 1, 5, 3, 9, 1 ] # Function call print(solve(arr)) # This code is contributed by Shivam Singh
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the minimum operations // to make the array Non-increasing static int solve(int []a) { // Size of the array int n = a.Length; // Dp table initialization int []dp = new int[n + 1]; int []val = new int[n + 1]; // dp[i]: Stores minimum number of // operations required to make // subarray {A[i], ..., A[N]} non-increasing for (int i = n - 1; i >= 0; i--) { int sum = a[i]; int j = i; while (j + 1 < n && sum < val[j + 1]) { // Increment the value of j j++; // Add current value to sum sum += a[j]; } // Update the dp tables dp[i] = (j - i) + dp[j + 1]; val[i] = sum; } // Return the answer return dp[0]; } // Driver code public static void Main(String[] args) { int []arr = { 1, 5, 3, 9, 1 }; Console.Write(solve(arr)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript program to implement // the above approach // Function to find the minimum operations // to make the array Non-increasing function solve(a) { // Size of the array let n = a.length; // Dp table initialization let dp = new Array(n+1).fill(0); let val = new Array(n+1).fill(0); // dp[i]: Stores minimum number of // operations required to make // subarray {A[i], ..., A[N]} non-increasing for (let i = n - 1; i >= 0; i--) { let sum = a[i]; let j = i; while (j + 1 < n && sum < val[j + 1]) { // Increment the value of j j++; // Add current value to sum sum += a[j]; } // Update the dp tables dp[i] = (j - i) + dp[j + 1]; val[i] = sum; } // Return the answer return dp[0]; } // Driver Code let arr = [ 1, 5, 3, 9, 1 ]; document.write(solve(arr)); </script>
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitpal210 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA