La Programación Dinámica ( DP ) es una técnica que resuelve algún tipo particular de problemas en Tiempo Polinomial. Las soluciones de Programación Dinámica son más rápidas que el método bruto exponencial y se puede probar fácilmente su exactitud. Antes de estudiar cómo pensar dinámicamente para un problema, necesitamos aprender:
Steps to solve a DP 1) Identify if it is a DP problem 2) Decide a state expression with least parameters 3) Formulate state relationship 4) Do tabulation (or add memoization)
Paso 1: ¿Cómo clasificar un problema como Problema de Programación Dinámica?
- Por lo general, todos los problemas que requieren maximizar o minimizar ciertas cantidades o problemas de conteo que dicen contar los arreglos bajo ciertas condiciones o ciertos problemas de probabilidad pueden resolverse usando Programación Dinámica.
- Todos los problemas de programación dinámica satisfacen la propiedad de subproblemas superpuestos y la mayoría de los problemas dinámicos clásicos también satisfacen la propiedad de subestructura óptima. Una vez que observamos estas propiedades en un problema dado, asegúrese de que se puede resolver usando DP.
Paso 2: Decidir el estado
Los problemas de DP tienen que ver con el estado y su transición. Este es el paso más básico que debe realizarse con mucho cuidado porque la transición de estado depende de la elección de definición de estado que realice. Entonces, veamos a qué nos referimos con el término “estado”.
Estado Un estado se puede definir como el conjunto de parámetros que pueden identificar de manera única una cierta posición o posición en el problema dado. Este conjunto de parámetros debe ser lo más pequeño posible para reducir el espacio de estado.
Por ejemplo: en nuestro famoso problema de la mochila , definimos nuestro estado mediante dos parámetros índice y peso, es decir, DP[índice][peso]. Aquí DP[índice][peso] nos dice la ganancia máxima que puede obtener al tomar artículos del rango 0 al índice que tiene la capacidad del saco para ser pesado. Por lo tanto, aquí los parámetros índice y peso juntos pueden identificar de manera única un subproblema para el problema de la mochila.
Entonces, nuestro primer paso será decidir un estado para el problema después de identificar que el problema es un problema de DP.
Como sabemos, DP tiene que ver con el uso de resultados calculados para formular el resultado final.
Entonces, nuestro próximo paso será encontrar una relación entre los estados anteriores para llegar al estado actual.
Paso 3: Formular una relación entre los estados
Esta parte es la parte más difícil de resolver un problema de PD y requiere mucha intuición, observación y práctica. Entendámoslo considerando un problema de muestra.
Given 3 numbers {1, 3, 5}, we need to tell
the total number of ways we can form a number 'N'
using the sum of the given three numbers.
(allowing repetitions and different arrangements).
Total number of ways to form 6 is: 8
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
Pensemos dinámicamente en este problema. Entonces, antes que nada, decidimos un estado para el problema dado. Tomaremos un parámetro n para decidir el estado, ya que puede identificar de forma única cualquier subproblema. Entonces, nuestro estado dp se verá como estado (n). Aquí, state(n) significa el número total de arreglos para formar n usando {1, 3, 5} como elementos.
Ahora, necesitamos calcular el estado (n).
¿Cómo hacerlo?
Así que aquí la intuición entra en acción. Como solo podemos usar 1, 3 o 5 para formar un número dado. Supongamos que conocemos el resultado para n = 1,2,3,4,5,6 ; siendo termilogísticos digamos que conocemos el resultado para el
estado (n = 1), estado (n = 2), estado (n = 3) ……… estado (n = 6)
Ahora, deseamos conocer el resultado de la estado (n = 7). Mira, solo podemos sumar 1, 3 y 5. Ahora podemos obtener una suma total de 7 de las siguientes 3 formas:
1) Sumar 1 a todas las posibles combinaciones de estado (n = 6)
Ej : [ (1+1+1+1+1+1) + 1]
[ (1+1+1+3) + 1]
[ (1 +1+3+1) + 1]
[ (1+3+1+1) + 1]
[ (3+1+1+1) + 1]
[ (3+3) + 1]
[ (1+5 ) + 1]
[ (5+1) + 1]
2) Sumar 3 a todas las posibles combinaciones de estado (n = 4);
Ej: [(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]
3) Sumar 5 a todas las combinaciones posibles de estado (n = 2)
Ej: [(1+1) + 5]
(Observe cómo es suficiente agregar solo en el lado derecho: todos los casos de agregar desde el lado izquierdo están cubiertos, ya sea en el mismo estado o en otro, por ejemplo, [ 1+(1+1+1+3)] no es necesario en el estado (n=6) porque está cubierto por el estado (n = 4) [(1+1+1+1) + 3])
Ahora, piense detenidamente y asegúrese de que los tres casos anteriores cubren todas las formas posibles de formar una suma total de 7;
Por lo tanto, podemos decir que resultado para
estado (7) = estado (6) + estado (4) + estado (2)
o
estado (7) = estado (7-1) + estado (7-3) + estado (7 -5)
En general,
estado (n) = estado (n-1) + estado (n-3) + estado (n-5)
Entonces, nuestro código se verá así:
C++
// Returns the number of arrangements to
// form 'n'
int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
return solve(n-1) + solve(n-3) + solve(n-5);
}
Java
// Returns the number of arrangements to
// form 'n'
static int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
return solve(n-1) + solve(n-3) + solve(n-5);
}
// This code is contributed by Dharanendra L V.
Python3
# Returns the number of arrangements to # form 'n' def solve(n): # Base case if n < 0: return 0 if n == 0: return 1 return (solve(n - 1) + solve(n - 3) + solve(n - 5)) # This code is contributed by GauriShankarBadola
C#
// Returns the number of arrangements to
// form 'n'
static int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
return solve(n-1) + solve(n-3) + solve(n-5);
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// Returns the number of arrangements to
// form 'n'
function solve(n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
return solve(n-1) + solve(n-3) + solve(n-5);
}
// This Code is Contributed by Harshit Srivastava
</script>
El código anterior parece exponencial ya que calcula el mismo estado una y otra vez. Entonces, solo necesitamos agregar memorización.
Paso 4: Agregar memorización o tabulación para el estado
Esta es la parte más fácil de una solución de programación dinámica. Solo necesitamos almacenar la respuesta del estado para que la próxima vez que se requiera ese estado, podamos usarlo directamente desde nuestra memoria.
Agregar memorización al código anterior
C++
// initialize to -1
int dp[MAXN];
// this function returns the number of
// arrangements to form 'n'
int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
// checking if already calculated
if (dp[n]!=-1)
return dp[n];
// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}
Java
// initialize to -1
public static int[] dp = new int[MAXN];
// this function returns the number of
// arrangements to form 'n'
static int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
// checking if already calculated
if (dp[n]!=-1)
return dp[n];
// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}
// This code is contributed by Dharanendra L V.
Python3
# This function returns the number of
# arrangements to form 'n'
# lookup dictionary/hashmap is initialized
def solve(n, lookup = {}):
# Base cases
# negative number can't be
# produced, return 0
if n < 0:
return 0
# 0 can be produced by not
# taking any number whereas
# 1 can be produced by just taking 1
if n == 0:
return 1
# Checking if number of way for
# producing n is already calculated
# or not if calculated, return that,
# otherwise calculate and then return
if n not in lookup:
lookup[n] = (solve(n - 1) +
solve(n - 3) +
solve(n - 5))
return lookup[n]
# This code is contributed by GauriShankarBadola
C#
// initialize to -1
public static int[] dp = new int[MAXN];
// this function returns the number of
// arrangements to form 'n'
static int solve(int n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
// checking if already calculated
if (dp[n]!=-1)
return dp[n];
// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// initialize to -1
let dp = new Array(MAXN);
// this function returns the number of
// arrangements to form 'n'
function solve(n)
{
// base case
if (n < 0)
return 0;
if (n == 0)
return 1;
// checking if already calculated
if (dp[n]!=-1)
return dp[n];
// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}
// This code is contributed by avanitrachhadiya2155
</script>
Otra forma es agregar tabulación y hacer que la solución sea iterativa. Consulte tabulación y memorización para obtener más detalles.
La programación dinámica viene con mucha práctica. Uno debe intentar resolver varios problemas clásicos de DP que se pueden encontrar aquí .
Primero puede verificar los problemas a continuación e intentar resolverlos siguiendo los pasos descritos anteriormente:
- http://www.spoj.com/problems/COINS/
- http://www.spoj.com/problemas/ACODE/
- https://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/
- https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
- https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
- https://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
Este artículo es una contribución de Nitish Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA