Examen Julio 2022, Ejercicio 2, parte b)

Examen Julio 2022, Ejercicio 2, parte b)

de Miguel Alejandro Piñero Espinoza -
Número de respuestas: 1

Buenas, queria consultar si la parte b) del ejercicio 2 del ejercicio de OPT esta correcto, como se detalla en la imagen el codigo de arriba a la izquierda es una solucion que deduje por la matriz auxiliar que me arme a la derecha. Mi duda principal es si es correcto la forma que recorri la matriz para ir armando la matriz OPT y el return OPT[n-1,n], debido a que en la solucion recorre de una forma distinta la matriz (solucion es el recorte de la imagen de abajo a la izquierda) y quiero saber si no importa esa forma de recorrerla. Gracias, saludos.


En respuesta a Miguel Alejandro Piñero Espinoza

Re: Examen Julio 2022, Ejercicio 2, parte b)

de Fernando Fernandez -
Hola.

Estás interpretando OPT como se sugiere en la letra, y además usás la relación de recurrencia de la parte (a), ¿no?

Si es así, me parce que hay dos indicios de que esa solución no es correcta.
Uno de ellos es que lo último que se calcula, y el valor que se devuelve, es OPT[n-1,n]. Pero este valor es 0 si los dos últimos caracteres son diferentes, y 2 si son iguales. Esta no puede ser la solución del problema porque no tiene en cuenta los primeros n-2 caracteres.

El otro problema, que explica este, es que en las líneas 7 y 9 para calcular OPT[i,j] hace falta tener ya calculado OPT[i+1, j-1] y OPT[i+1,j]. pero esos valores todavía no se calcularon.

¿Se entiende?

Saludos,