Este es un problema clásico de DP.
Introducción a DP para principiantes: la programación dinámica es una técnica en la que aceleramos el cálculo de una función recursiva que se puede dividir en subproblemas que se superponen (por ejemplo, la función de Fibonacci tiene muchos subproblemas superpuestos. Dibuje el árbol de recursión para fib (5) y verás cuántas veces aparecerá fib (3)). La forma de acelerar el cálculo implica almacenar subproblemas que ya se han calculado en una matriz de notas . De esta manera, cada vez que tengamos que calcular el mismo subproblema nuevamente, en lugar de bajar su árbol de recursión, simplemente devolvemos el valor almacenado en la matriz.
long long int memo [100];
largo largo int fib (int n)
{
if (memo [n] == -1) // aún no calculado
{
if (n == 0 || n == 1) memo [n] = 1;
else memo [n] = fib (n-1) + fib (n-2);
}
volver memo [n];
}
- ¿Cuáles son los buenos canales en YouTube para aprender algoritmos y estructuras de datos para la preparación de Google Code Jam o Facebook Hacker Cup?
- ¿Por qué necesito el complemento de un gráfico?
- ¿Cuál es el enfoque para resolver la interpretación de datos en CAT? ¿Se usa lápiz y papel para dibujar estructuras o se mantiene al mínimo?
- Cómo hacer que el siguiente código sea mejor y más eficiente para el problema de invertir las palabras en la oración dada
- ¿Cómo se relacionan el comercio algorítmico y de alta frecuencia y la teoría de gráficos?
Ahora, para nuestro problema gráfico. Podemos definir la siguiente función recursiva para encontrar la ruta más pesada desde una fuente s hasta un destino t en un DAG:
Sea w [v] el peso del vértice v y h (v) el camino más pesado que comienza en el vértice v y termina en t, luego:
h (v) = w [v] si v == t
h (v) = max (w [v] + h (u) para cada u en adj [v]) de lo contrario
Podemos ver que esta función recursiva calculará algunos subproblemas muchas veces (superposición), por lo que podemos usar una matriz que almacenará los valores de h (v) ya calculados para evitar el recálculo:
int memo [MAX_NODES], w [MAX_NODES];
int s, t;
int h (int v)
{
if (v == t) devuelve w [v];
if (memo [v] == -1)
{
for (auto u: adj [v]) // cada u adyacente a v
memo [v] = max (memo [v], w [v] + h (u));
}
volver memo [v];
}
int main ()
{
// … lee tu entrada y construye el gráfico …
// … despeja la matriz de notas poniendo -1 en cada posición …
cout << "la ruta más pesada es" << h (s) << endl;
}
Como la función anterior encuentra la ruta más pesada que comienza en el vértice de origen, podemos verificar fácilmente si es mayor que k o no. El tiempo de ejecución de esta función es O (N + M). Dejaré la prueba como ejercicio 🙂
