Encontrando Mutaciones (ADN)
Este problema creo que se lo puede considerar “clásico”, o al menos está MUY relacionado con el problema de Edit Distance (que es la distancia entre strings que define el enunciado, por si se quiere googlear al respecto).
Como muchas otras veces donde usamos programación dinámica, la idea es resolver el problema, suponiendo que sabemos resolver pedacitos más pequeños. En este caso, vamos a pensar el problema suponiendo que ya lo sabemos resolver para los prefijos de cada palabra (les voy a llamar s a la primera y t a la segunda).
Es decir, vamos a plantear:
\texttt{f}({\color{cyan}{i}},{\color{magenta}{j}}) = \texttt{distancia entre } \overset{\text{prefijo}}{\overbrace{ {\color{cyan}{\texttt{s}\texttt{[0..i)}}} } } \texttt{ y } \overset{\text{prefijo}}{\overbrace{ {\color{magenta}{\texttt{t}\texttt{[0..j)}}} } }
\begin{matrix}
s_1& s_2 & \dots & s_{i-1} & | & {\color{cyan}{s_i} } & | & s_{i+1} & \dots & s_N
\end{matrix}
\begin{matrix}
t_1 & t_2 & \dots & t_{j-1} & | & {\color{magenta}{t_j} } & | & t_{j+1} & \dots & t_M
\end{matrix}
Esta \texttt{f} depende solo de los estados:
-
(i-1,j) (borrar el s[i])
-
(i,j-1) (agregar t[j] después de s[i])
-
(i-1,j-1) (reemplazar s[i] por t[j])
Con esta idea, creo que debería estar más claro cómo obtener una solución que corra en \mathcal{O}(NM) (N y M como en el enunciado).
Vamos a diferenciar el tiempo de corrida del espacio usado en memoria. El enfoque usual usa \mathcal{O}(NM) de tiempo y también \mathcal{O}(NM) de memoria (porque se guarda toda la tabla)
¿Cómo podemos mejorar el \mathcal{O}(NM) en memoria? (el de tiempo no todavía)
La gracia es que si vamos llenando en orden los j, para llenar (1,j) solo necesitamos estados de la pinta (0,j) o (1,j) con j anteriores. Para llenar el (2,j) solo necesitamos los (1,j) o (2,j) con los j anteriores. Entonces si vamos llenando en orden creciente en i, para resolver todos los nodos de la pinta (i,j) solo nos hace falta la “capa” anterior (la capa de todos los (i-1,j) ).
En la “tabla” esto nos dice que al llenar la fila i, solo nos hace falta conocer los valores de la fila i-1 y la fila i que vamos llenando.
Entonces si en lugar de guardarnos tooooda la tabla, solo nos guardamos las últimas dos filas que vamos procesando, nos podemos ahorrar memoria (y usar solo \mathcal{O}(N) u \mathcal{O}(M) memoria)
¿Cómo podemos usar el K en todo esto para bajar el tiempo?¿Hace falta mirar toda la tabla?
Para pensar en términos de la tabla probablemente es más fácil mirar las transiciones al revés (me resulta más natural bajar hacia la derecha que subir a la izquierda). Los movimientos posibles son 3:
(i,j)) \rightarrow \{\overset{\text{diagonal } \searrow}{\overbrace{(i+1,j+1)}},\underset{\text{bajar } \downarrow}{\underbrace{(i+1,j)}},\underset{{\normalsize\text{derecha }} \rightarrow }{\underbrace{(i,j+1)}} \}
O sea, si estamos en la fila i y la columna j podemos movernos en esas 3 direcciones. Pero en las de bajar y moverse a la derecha, pagamos costo 1 siempre (en diagonal depende de si coinciden las letras o no). Por lo tanto en las soluciones que nos interesan, jamás se realizan más de K de estos movimientos (notar que el K es chiquito).
Entonces alcanza con ver qué pasa en los lugares que podemos alcanzar. Por ejemplo, esto sería con K = 1, con K más grandes la banda que hay que mirar se agranda:
De esta forma, solo visitamos \mathcal{O}(KN) estados.
