Optimizaciones y técnicas adicionales de DP

Optimización de Knuth

Tutoriales

La Optimización de Knuth es un caso especial de DP de rangos. En general, se usa para resolver problemas de DP con transiciones de la forma

Además, la función de costo debe satisfacer las siguientes condiciones para todo $a\leq b\leq c \leq d$:

1. $\texttt{cost}[b][c] \leq \texttt{cost}[a][d]$
2. $\texttt{cost}[a][c] + \texttt{cost}[b][d] \leq \texttt{cost}[a][d] + \texttt{cost}[b][c]$ (la desigualdad del cuadrángulo)

Definimos $\texttt{opt}[i][j]$ como el índice para el cual $\texttt{dp}[i][k] + \texttt{dp}[k+1][j]$ alcanza su valor mínimo, o de forma equivalente,

Si existe más de un índice así, tomamos el mínimo (o el máximo; no importa). Entonces, asumiendo que se cumplen las condiciones sobre la transición de DP y la función de costo, se puede demostrar que $\texttt{opt}$ satisface

La demostración de corrección de esta afirmación está en los recursos de arriba.

La estructura del código es idéntica a la de DP de rangos , con la excepción de mantener el arreglo $\texttt{opt}$. Para calcular $\texttt{dp}[i][j]$ y $\texttt{opt}[i][j]$, solo hace falta revisar valores de $k$ entre $\texttt{opt}[i][j-1]$ y $\texttt{opt}[i+1][j]$. Por la monotonicidad de $\texttt{opt}$, se puede demostrar que la complejidad temporal del algoritmo final es $\mathcal{O}(N^2)$.

Problemas de Optimización de Knuth

DP de componentes conexas

Problemas de DP de componentes conexas