=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
2024/2025
Ejercicio 13 del Tema 5.3 (opcional)
Borrador
=================================================================



(a) Algoritmo recursivo eficiente empleando Programacion Dinamica
=================================================================

En este pseudocodigo suponemos que los argumentos de tipo secuencia y
matriz se pasan por referencia. La matriz se indexa desde 0 y las
secuencias se indexan desde 1. Si x es de tipo secuencia su longitud
es x.longitud() y sus elementos van desde x[1] hasta x[x.longitud()].

_______________________________________________________________________________________________
entero LCS(secuencia A, secuencia B) :

   Crear una matriz resultado de dimensiones (A.longitud() + 1) x (B.longitud() + 1)
   Inicializar resultado con -1 en todas sus celdas
   devolver LCS(A, B, A.longitud(), B.longitud(), resultado)

_______________________________________________________________________________________________
entero LCS(secuencia A, secuencia B, entero posicionA, entero posicionB, matriz resultado) :

   si resultado[posicionA][posicionB] == -1 :

      si posicionA == 0 o posicionB == 0 :
         resultado[posicionA][posicionB] = 0

      sino si A[posicionA] == B[posicionB] :
         resultado[posicionA][posicionB] = 1 + LCS(A, B, posicionA - 1, posicionB - 1, resultado)

      sino :
         resultado[posicionA][posicionB] = max(LCS(A, B, posicionA - 1, posicionB, resultado),
                                               LCS(A, B, posicionA, posicionB - 1, resultado))

   devolver resultado[posicionA][posicionB]
_______________________________________________________________________________________________


(b) Algoritmo no recursivo eficiente empleando Programacion Dinamica
====================================================================

________________________________________________________________________________________
entero LCS(secuencia A, secuencia B) :

   Crear una matriz resultado de dimensiones (A.longitud() + 1) x (B.longitud() + 1)

   para posicionA desde 0 hasta A.longitud() :

      para posicionB desde 0 hasta B.longitud() :

         si posicionA == 0 o posicionB == 0 :
            resultado[posicionA][posicionB] = 0

         sino si A[posicionA] == B[posicionB] :
            resultado[posicionA][posicionB] = 1 + resultado[posicionA - 1][posicionB - 1]

         sino :
            resultado[posicionA][posicionB] = max(resultado[posicionA - 1][posicionB],
                                                  resultado[posicionA][posicionB - 1])

   devolver resultado[A.longitud()][B.longitud()]
________________________________________________________________________________________


(c) Coste temporal y espacial de ambos algoritmos
=================================================

O(n m) siendo n y m las longitudes de las dos secuencias dadas.