¿Cómo resolver una pregunta de IOIPALIN en Spoj? ¿Cómo optimizo el espacio?

Answer 1

La lógica DP para este problema es como la matriz 2D DP utilizada para otros problemas relacionados con el palíndromo, pero con la optimización del espacio mediante el uso de la matriz N * 2. (N – longitud de la cuerda)

Primero contaré la lógica usando la matriz N * N.
Básicamente almacenaremos valores en celdas de tal manera que la celda (i, j) almacene el número de adiciones requeridas para hacer que la subcadena (i, j) sea un palíndromo.
1. Inicialice todos los elementos diagonales con 0s.
2. Inicialice (i, i + 1) celdas a 0 si str [i] == str [i + 1] más 1.
3. Ahora itera para la longitud L = 3 a N.

• Para cada iteración, debemos considerar todas las subcadenas de L, digamos str [i, j].
• Ahora, si str [i] == str [j], entonces la celda de la matriz debe establecerse en el valor de (i + 1, j-1) más valor de (i + 1, j-1) + 2. Porque si str [ i]! = str [j] luego para hacer str [i, j] un palíndromo, necesitamos agregar dos caracteres más. Además de caracteres adicionales necesarios para hacer str [i + 1, j-1] un palíndromo.

4. Finalmente, un valor en (0, N-1) será la respuesta.

Ahora, para optimizar el espacio, use la matriz N * 2, donde ambas columnas se usan indistintamente para almacenar el estado actual (para la longitud L) y el anterior (para la longitud L-1), es decir, inicialmente la columna 0 almacenará valores para la longitud 1 y la columna 1 para la longitud 2. Ahora para la longitud 3, usaremos la columna 0 para almacenar todos los valores y nuevamente la columna 1 para almacenar los valores para la longitud 4 usando los valores en la columna 0.
¡Imagínese la diagonal en la matriz N * N anterior como columna 0 de esta nueva matriz N * 2 y la obtendrá!