Podría decirse que la programación dinámica (DP) es la herramienta más importante en el repertorio de un programador competitivo. Hay varias optimizaciones en DP que reducen la complejidad temporal de los procedimientos de DP estándar en un factor lineal o más, como la optimización de Knuth , la optimización Divide and Conquer , el truco del casco convexo, etc. Son de suma importancia para la programación competitiva avanzada, como a nivel de olimpiadas. En este artículo, descubriremos la optimización divide y vencerás, que NO debe confundirse con el algoritmo divide y vencerás para resolver problemas.
Criterios de optimización de divide y vencerás:
La optimización divide y vencerás se puede usar para problemas con una transición dp de la siguiente forma:
dp[i][j] = min 1≤k<j (dp[i-1][k-1] + costo[k][j])
Además, la función de costo debe satisfacer la desigualdad cuadrángulo (QI), es decir,
costo(a, c) + costo(b, d) ≤ costo(a, d) + costo(b, c) para todo a ≤ b ≤ c ≤ d.
Técnica de optimización divide y vencerás:
El enfoque subóptimo para resolver cualquier problema con una transición de programación dinámica de la forma dada anteriormente iteraría a través de todos los valores posibles de k < j para cada transición. Entonces, si las restricciones del problema dan 1 ≤ i ≤ m y 1 ≤ j ≤ n , el algoritmo tomará O(mn 2 ) tiempo.
La clave de la optimización es la siguiente:
- Al igual que en la optimización de Knuth , defina la función opt(i, j) , el valor mínimo (o máximo, no importa) de k para el cual dp[i][j] toma su valor mínimo. Entonces, tenemos la siguiente relación:
opt[i][j] ≤ opt[i][j+1] , donde
opt[i][j] = argmin k<j (dp[i-1][k] + costo[k][j])
Ahora, supongamos que calculamos opt[i][j] para algunos i y j . Entonces, también sabemos que opt[i][p] ≤ opt[i][j] para todo p < j . La solución subóptima implicaría hacer un bucle para cada j , a través de todos los valores posibles de k para cualquier i fijo . La optimización en sí es la siguiente:
- Recorra los valores de i , y primero calcule dp[i][j] y opt[i][j] para j = n/2 , para el i actual . Esto es posible ya que en el momento del procesamiento conocemos todos los valores de la tabla dp para dp[i-1][k] para todo k ≤ n , debido a la estructura del bucle.
- Ahora, calcule dp[i][n/4] y dp[i][3n/4] , sabiendo que opt[i][n/4] ≤ opt[i][n/2] y opt[i][ n/2] ≤ opt[i][3n/4] .
- De forma recursiva, llamamos a esta función de resolución, haciendo un seguimiento de los límites inferior y superior de opt[i][j] para alguna i y la j actual . Por ejemplo, al calcular dp[i][5n/8] , sabemos que opt[i][n/2]≤ opt[i][5n/8] ≤ opt[i][3n/4] .
El algoritmo es más rápido por un factor lineal, ya que no tenemos que recorrer todos los valores de k , y se agrega un factor logarítmico debido a la naturaleza recursiva de este algoritmo. La complejidad del tiempo es por tanto O(m * n * (log n)) .
El código genérico para este enfoque se proporciona a continuación. Utiliza un enfoque recursivo, que es el más simple de implementar dada la estructura de la solución.
C++
// C++ code for generic approach
// of the divide and conquer optimization
#include <bits/stdc++.h>
using namespace std;
const int MAX_M = 10005;
const int MAX_N = 1005;
int N, M, dp[MAX_M][MAX_N], cost[MAX_M][MAX_M];
// Function to perform the decide and conquer
void divide(int l, int r, int optl,
int optr, int i)
{
if (l > r)
return;
// Find middle value
int mid = (l + r) >> 1;
// Store the minimum cost and opt(i, j)
pair<int, int> best = {INT_MAX, -1};
// Find the value of the best cost and opt(i, j)
for (int k = optl; k < min(mid, optr); k++)
best = min(best, {(k ? dp[i-1][k] : 0)
+ cost[k][mid], k});
// Store the minimum cost in the dp array
dp[i][mid] = best.first;
int opt = best.second;
// Recursively call the divide function
// to fill the other dp states
divide(l, mid - 1, optl, opt, i);
divide(mid + 1, r, opt, optr, i);
}
void solve()
{
// Initial state of the dp table
// Normally table is initialized for j=0
// or j=1 depending on problem statement
for (int i = 0; i < N; i++)
dp[0][i] = cost[0][i];
// Fill in the dp array
// with the divide function
for (int i = 1; i < M; i++)
divide(0, N - 1, 0, N - 1, i);
cout << dp[M-1][N-1] << endl;
}
int main() \
{
// Take the required inputs
solve();
return 0;
}
Prueba de corrección de la optimización Divide and Conquer:
Para probar la exactitud de este algoritmo, solo necesitamos probar la desigualdad:
optar[i][j] ≤ optar[i][j+1]
Siga la sección a continuación para obtener una prueba de corrección:
Supuestos: Si cost(i, j) satisface la Desigualdad del Cuadrángulo, entonces dp[i][j] también satisface la desigualdad.
Ahora, considere la siguiente configuración:
- Tenemos algunos índices 1 ≤ p ≤ q ≤ j y un i fijo separado .
- Sea dp k [i][j] = costo[k][i] + dp[k-1][j-1].
Si podemos demostrar que –
dp p [i][j] ≥ dp q [i][j] ⇒ dp p [i][j+1] ≥ dp q [i][j+1]
luego, al establecer q = opt[i][j] , quedará claro que opt[i][j+1] será al menos tanto como opt[i][j] , debido a la implicación de la desigualdad anterior para todos los índices p menores que opt[i][j] . Esto probará que opt[i][j-1] ≤ opt[i][j] .
Prueba:
De la desigualdad Quadrangle en la array dp obtenemos:
costo(p, j) + costo(q, j+1) ≤ costo(p, j+1) + costo(q, j)
⇒ (dp[i-1, p] + costo(p, j)) + (dp[i-1, q] + costo(q, j+1)) ≤ (dp[i-1, p] + costo(p, j+1)) + (dp[j-1, q] + costo(q, j))
⇒ dp p [i][j] + dp q [i][j+1] ≤ dp p [i][j+1] + dp q [i][j]
⇒ dp p [i][j] – dp q [i][j] ≤ dp p [i][j+1] – dp q [i][j+1]dp p [i][j] ≥ dp q [i][j]
⇒ 0 ≤ dp p [i][j] – dp q [i][j] ≤ dp p [i][j+1] – dp q [i][j+1]
⇒ dp p [i][j+1] ≥ dp q [i][j+1]Esto completa la prueba dp p [i][j] ≥ dp q [i][j] ⇒ dp p [i][j+1] ≥ dp q [i][j+1]
Ejemplos para mostrar el funcionamiento de la optimización divide y vencerás:
Dada una array arr[] de N elementos, la tarea es dividirla en K subarreglos, de modo que la suma de los cuadrados de las sumas de los subarreglos se minimice.
Ejemplos:
Entrada: array []= {1, 3, 2, 6, 7, 4}, K = 3 .
Salida: 193
Explicación: La división óptima en subarreglos es [1, 3, 2], [6] y [7, 4],
dando una suma total de (1 + 3 + 2) 2 + (6) 2 + (7 + 4) 2 = 193.
Esta es la suma mínima posible para esta array en particular y K.Entrada: arr[] = {1, 4, 2, 3}, K = 2
Salida: 50
Explicación: Divídalo en subarreglos {1, 4} y {2, 3}.
La suma es (1+4) 2 + (2 + 3) 2 = 5 2 + 5 2 = 50.
Esta es la suma mínima posible.
Solución subóptima: El problema se puede resolver en base a la siguiente idea:
- Si los primeros j-1 elementos se dividen en i-1 grupos, entonces el costo mínimo de dividir los primeros j elementos en i grupos es el mismo que el valor mínimo entre todas las combinaciones posibles de dividir los primeros k-1 (i ≤ k ≤ j) elementos en i-1 grupos y el coste del i-ésimo grupo formado tomando elementos de k -ésimo a j- ésimo índices.
- Sea dp[i][j] la suma mínima que se puede obtener dividiendo los primeros j elementos en i subarreglos.
Así que la transición dp será:dp[i][j] = min i≤k≤j (dp[i-1][k-1] + costo[k][i])
donde cost[k][i] denota el cuadrado de la suma de todos los elementos en el subarreglo arr [k, k+1 . . . i]
Siga los pasos que se mencionan a continuación para resolver el problema:
- La función de costo se puede calcular en tiempo constante preprocesando usando una array de suma de prefijos :
- Calcule la suma de prefijos (digamos almacenados en la array pref[]).
- Entonces, el costo (i, j) se puede calcular como (pref [j] – pref [i-1]).
- Travesía de i = 1 a M:
- Travesía de j = i a N:
- Recorra usando k y forme la tabla dp[][] usando la observación dp anterior.
- El valor en dp[M-1][N-1] es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum sum
int solve(int arr[], int N, int M)
{
int pref[N + 1], dp[M + 1][N + 1];
// Prefix sum array
pref[0] = 0;
for (int i = 0; i < N; i++)
pref[i + 1] = pref[i] + arr[i];
// Initialize the dp array
for (int i = 0; i < N; i++)
dp[0][i] = pref[i + 1] * pref[i + 1];
// Fill in the dp array
for (int i = 1; i < M; i++) {
for (int j = i; j < N; j++) {
dp[i][j] = INT_MAX;
for (int k = 1; k <= j; k++) {
int cost
= (pref[j + 1] - pref[k])
* (pref[j + 1] - pref[k]);
// dp transition
dp[i][j] = min(dp[i][j],
dp[i - 1][k - 1]
+ cost);
}
}
}
return dp[M - 1][N - 1];
}
// Driver code
int main()
{
int N, M = 3;
int arr[] = { 1, 3, 2, 6, 7, 4 };
N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << solve(arr, N, M);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
class GFG {
// Function to find the minimum sum
public static int solve(int arr[], int N, int M)
{
int pref[] = new int[N + 1];
int dp[][] = new int[M + 1][N + 1];
// Prefix sum array
pref[0] = 0;
for (int i = 0; i < N; i++)
pref[i + 1] = pref[i] + arr[i];
// Initialize the dp array
for (int i = 0; i < N; i++)
dp[0][i] = pref[i + 1] * pref[i + 1];
// Fill in the dp array
for (int i = 1; i < M; i++) {
for (int j = i; j < N; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int k = 1; k <= j; k++) {
int cost = (pref[j + 1] - pref[k])
* (pref[j + 1] - pref[k]);
// dp transition
dp[i][j] = Math.min(
dp[i][j], dp[i - 1][k - 1] + cost);
}
}
}
return dp[M - 1][N - 1];
}
// Driver Code
public static void main(String[] args)
{
int N, M = 3;
int arr[] = { 1, 3, 2, 6, 7, 4 };
N = arr.length;
// Function call
System.out.print(solve(arr, N, M));
}
}
// This code is contributed by Rohit Pradhan
Python3
import sys # Function to find the minimum sum def solve(arr, N, M) : pref = [0] * (N + 1) dp = [[0] * (N + 1) ] * (M+1) # Prefix sum array pref[0] = 0 for i in range(N) : pref[i + 1] = pref[i] + arr[i] # Initialize the dp array for i in range(N) : dp[0][i] = pref[i + 1] * pref[i + 1] # Fill in the dp array for i in range(1, M) : for j in range(i, N) : dp[i][j] = -193 for k in range(1, j+1) : cost = ((pref[j + 1] - pref[k]) * (pref[j + 1] - pref[k])) # dp transition dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + cost); return (-dp[M - 1][N - 1]) # Driver code if __name__ == "__main__": N = 3 M = 3 arr = [ 1, 3, 2, 6, 7, 4 ] N = len(arr) # Function call print(solve(arr, N, M)) # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum sum
static int solve(int[] arr, int N, int M)
{
int[] pref = new int[N + 1];
int[,] dp = new int[M + 1, N + 1];
// Prefix sum array
pref[0] = 0;
for (int i = 0; i < N; i++)
pref[i + 1] = pref[i] + arr[i];
// Initialize the dp array
for (int i = 0; i < N; i++)
dp[0, i] = pref[i + 1] * pref[i + 1];
// Fill in the dp array
for (int i = 1; i < M; i++) {
for (int j = i; j < N; j++) {
dp[i, j] = Int32.MaxValue;
for (int k = 1; k <= j; k++) {
int cost = (pref[j + 1] - pref[k])
* (pref[j + 1] - pref[k]);
// dp transition
dp[i, j] = Math.Min(
dp[i, j], dp[i - 1, k - 1] + cost);
}
}
}
return dp[M - 1, N - 1];
}
// Driver Code
public static void Main(String[] args)
{
int N, M = 3;
int[] arr = { 1, 3, 2, 6, 7, 4 };
N = arr.Length;
// Function call
Console.WriteLine(solve(arr, N, M));
}
}
// This code is contributed by code_hunt.
193
Complejidad de Tiempo: O(M * N 2 )
Espacio Auxiliar: O(M * N)
Solución óptima (utilizando la optimización Divide and Conquer):
Este problema sigue el cuadrángulo Sin embargo, podemos notar que la función de costo satisface la desigualdad del cuadrángulo
costo(a, c) + costo(b, d) ≤ costo(a, d) + costo(b, c).
La siguiente es la prueba:
Sea sum(p, q) denote la suma de valores en el rango [p, q] (sub-arreglo de arr[[]), y sea x = sum(b, c) , y = sum(a, c) − suma(b, c), y z = suma(b, d) − suma(b, c) .
Usando esta notación, la desigualdad cuadrángulo se convierte en
(x + y) 2 + (x + z) 2 ≤ (x + y + z) 2 + x 2 ,
lo que equivale a 0 ≤ 2yz.Dado que y y z son valores no negativos, esto completa la demostración. Por lo tanto, podemos utilizar la optimización divide y vencerás.
- Hay una capa más de optimización en la complejidad del espacio que podemos hacer. Para calcular los estados dp[][] para un cierto valor de j , solo necesitamos los valores del estado dp para j-1 .
- Por lo tanto, mantener 2 arrays de longitud N e intercambiarlas después de que la array dp[][] se haya llenado con el valor actual de j elimina un factor de K de la complejidad del espacio.
Nota: Esta optimización se puede utilizar para todas las implementaciones de la aceleración de DP divide y vencerás.
Siga los pasos mencionados a continuación para implementar la idea:
- La función de costo se puede calcular utilizando el prefijo suma como en el enfoque anterior.
- Ahora, para cada valor fijo de i (número de subarreglos en los que se divide el arreglo):
- Recorre toda la array para encontrar la suma mínima posible para i divisiones.
- El valor almacenado en dp[M%2][N-1] es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to implement the
// divide and conquer optimization
void divide(int l, int r, int optl, int optr,
int i, vector<vector<int>> &dp,
int pref[])
{
if (l > r)
return;
// Find middle value
int mid = (l + r) >> 1;
// Store the minimum cost and opt(i, j)
pair<int, int> best = {INT_MAX, -1};
// Find value of the best cost and opt(i, j)
for (int k = optl; k <= min(mid, optr);
k++) {
int cost = (pref[mid+1] - pref[k])
* (pref[mid+1] - pref[k]);
best = min(best,
{(k ? dp[(i+1)%2][k-1] : 0)
+ cost, k});
}
// Store the minimum cost in the dp array
dp[i][mid] = best.first;
int opt = best.second;
// Recursively call the divide function
// to fill the other dp states
divide(l, mid - 1, optl, opt, i, dp, pref);
divide(mid + 1, r, opt, optr, i, dp, pref);
}
// Function to solve the problem
int solve(int arr[], int N, int M)
{
vector<vector<int>> dp(2, vector<int>(N));
// Prefix sum array
int pref[N + 1];
pref[0] = 0;
for (int i = 0; i < N; i++)
pref[i + 1] = pref[i] + arr[i];
// Initialize the dp array
for (int i = 0; i < N; i++)
dp[1][i] = pref[i + 1] * pref[i + 1];
// Fill in the dp array
// with the divide function
for (int i = 2; i <= M; i++)
divide(0, N - 1, 0, N - 1,
(i%2), dp, pref);
return dp[M%2][N-1];
}
// Driver code
int main()
{
int N, M = 3;
int arr[] = { 1, 3, 2, 6, 7, 4 };
N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << solve(arr, N, M);
return 0;
}
193
Complejidad de Tiempo: O (M * N * logN)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por omkarbajaj000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA