Memoización (1D, 2D y 3D)

La mayoría de los problemas de Programación Dinámica se resuelven de dos formas:  

1. Tabulación: de abajo hacia arriba
2. Memoización: de arriba hacia abajo

Uno de los enfoques más fáciles para resolver la mayoría de los problemas en DP es escribir el código recursivo al principio y luego escribir el método de tabulación de abajo hacia arriba o la memorización de arriba hacia abajo de la función recursiva. Los pasos para escribir la solución DP del enfoque de arriba hacia abajo para cualquier problema son:  

1. Escribe el código recursivo
2. Memoice el valor de retorno y utilícelo para reducir las llamadas recursivas.

Memoización 1-D
El primer paso será escribir el código recursivo. En el programa a continuación, se muestra un programa relacionado con la recursividad donde solo un parámetro cambia su valor. Dado que solo un parámetro no es constante, este método se conoce como memorización 1-D. Por ejemplo, el problema de la serie de Fibonacci para encontrar el N-ésimo término en la serie de Fibonacci. El enfoque recursivo se ha discutido aquí .
A continuación se muestra el código recursivo para encontrar el N-ésimo término:  

// C++ program to find the Nth term
// of Fibonacci series
#include <bits/stdc++.h>
using namespace std;
 
// Fibonacci Series using Recursion
int fib(int n)
{
 
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) + fib(n - 2);
}
 
// Driver Code
int main()
{
    int n = 6;
    printf("%d", fib(n));
    return 0;
}

// Java program to find the
// Nth term of Fibonacci series
import java.io.*;
 
class GFG
{
     
// Fibonacci Series
// using Recursion
static int fib(int n)
{
 
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) +
           fib(n - 2);
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 6;
    System.out.println(fib(n));
}
}
 
// This code is contributed
// by ajit

# Python3 program to find the Nth term
# of Fibonacci series
 
# Fibonacci Series using Recursion
def fib(n):
 
 
    # Base case
    if (n <= 1):
        return n
 
    # recursive calls
    return fib(n - 1) + fib(n - 2)
 
# Driver Code
if __name__=='__main__':
    n = 6
    print (fib(n))
  
# This code is contributed by
# Shivi_Aggarwal

// C# program to find
// the Nth term of
// Fibonacci series
using System;
 
class GFG
{
     
// Fibonacci Series
// using Recursion
static int fib(int n)
{
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) +
           fib(n - 2);
}
// Driver Code
static public void Main ()
{
    int n = 6;
    Console.WriteLine(fib(n));
}
}
 
// This code is contributed
// by akt_mit

<script>
// Javascript program to find the Nth term
// of Fibonacci series
 
// Fibonacci Series using Recursion
function fib(n)
{
 
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) + fib(n - 2);
}
 
// Driver Code
let n = 6;
document.write(fib(n));
 
// This code is contributed by subhammahato348.
</script>

<?php
// PHP program to find
// the Nth term of
// Fibonacci series
// using Recursion
 
function fib($n)
{
 
    // Base case
    if ($n <= 1)
        return $n;
 
    // recursive calls
    return fib($n - 1) +
           fib($n - 2);
}
 
// Driver Code
$n = 6;
echo fib($n);
 
// This code is contributed
// by ajit
?>

8

Una observación común es que esta implementación hace mucho trabajo repetido (vea el siguiente árbol de recursión). Así que esto consumirá mucho tiempo para encontrar el N-ésimo número de Fibonacci si se hace.  

                            fib(5)   
                     /                 \        
               fib(4)                  fib(3)   
             /      \                /       \
         fib(3)      fib(2)         fib(2)    fib(1)
        /   \          /    \       /      \ 
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \ 
fib(1) fib(0) 

In the above tree fib(3), fib(2), fib(1), fib(0) all are called more than once.

El siguiente problema se ha resuelto utilizando el método  de Tabulación . En el programa a continuación, se han explicado
los pasos para escribir un programa de enfoque de arriba hacia abajo . Algunas modificaciones en el programa recursivo reducirán la complejidad del programa y darán el resultado deseado. Si fib(x) no ha ocurrido anteriormente, entonces almacenamos el valor de fib(x) en un término de array en el índice x y devolvemos term[x] . Al memorizar el valor de retorno de fib(x) en el índice x de una array, reduzca la cantidad de llamadas recursivas en el siguiente paso cuando ya se haya llamado a fib(x). Entonces, sin hacer más llamadas recursivas para calcular el valor de fib(x), devolver el término[x] cuando fib(x)ya ha sido calculado previamente para evitar mucho trabajo repetido como se muestra en el árbol. 
A continuación se muestra el código recursivo memorizado para encontrar el N-ésimo término.  

// CPP program to find the Nth term
// of Fibonacci series
#include <bits/stdc++.h>
using namespace std;
int term[1000];
// Fibonacci Series using memoized Recursion
int fib(int n)
{
    // base case
    if (n <= 1)
        return n;
 
    // if fib(n) has already been computed
    // we do not do further recursive calls
    // and hence reduce the number of repeated
    // work
    if (term[n] != 0)
        return term[n];
 
    else {
 
        // store the computed value of fib(n)
        // in an array term at index n to
        // so that it does not needs to be
        // precomputed again
        term[n] = fib(n - 1) + fib(n - 2);
 
        return term[n];
    }
}
 
// Driver Code
int main()
{
    int n = 6;
    printf("%d", fib(n));
    return 0;
}

// Java program to find
// the Nth term of
// Fibonacci series
import java.io.*;
 
class GFG
{
 
static  int []term = new int [1000];
// Fibonacci Series using
// memoized Recursion
static int fib(int n)
{
    // base case
    if (n <= 1)
        return n;
 
    // if fib(n) has already
    // been computed we do not
    // do further recursive
    // calls and hence reduce
    // the number of repeated
    // work
    if (term[n] != 0)
        return term[n];
 
    else
    {
 
        // store the computed value
        // of fib(n) in an array
        // term at index n to so that
        // it does not needs to be
        // precomputed again
        term[n] = fib(n - 1) +
                  fib(n - 2);
 
        return term[n];
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 6;
    System.out.println(fib(n));
}
}
 
// This code is contributed by ajit

# Python program to find the Nth term
# of Fibonacci series
term = [0 for i in range(1000)]
 
# Fibonacci Series using memoized Recursion
def fib(n):
   
  # base case
  if n <= 1:
    return n
 
  # if fib(n) has already been computed
  # we do not do further recursive calls
  # and hence reduce the number of repeated
  # work
  if term[n] != 0:
    return term[n]
 
  else:
     
    # store the computed value of fib(n)
    # in an array term at index n to
    # so that it does not needs to be
    # precomputed again
    term[n] = fib(n - 1) + fib(n - 2)
    return term[n]
 
# Driver Code
n = 6
print(fib(n))
 
# This code is contributed by rohitsingh07052

// C# program to find
// the Nth term of
// Fibonacci series
 
using System;
class GFG
{
      
// Fibonacci Series using
// memoized Recursion
static int fib(int n)
{
    int[] term = new int [1000];
      
    // base case
    if (n <= 1)
        return n;
  
    // if fib(n) has already
    // been computed we do not
    // do further recursive
    // calls and hence reduce
    // the number of repeated
    // work
    if (term[n] != 0)
        return term[n];
  
    else
    {
  
        // store the computed value
        // of fib(n) in an array
        // term at index n to so that
        // it does not needs to be
        // precomputed again
        term[n] = fib(n - 1) +
                  fib(n - 2);
  
        return term[n];
    }
}
  
// Driver Code
public static void Main ()
{
    int n = 6;
    Console.Write(fib(n));
}
}

<script>
    // Javascript program to find
    // the Nth term of
    // Fibonacci series
     
    // Fibonacci Series using
    // memoized Recursion
    function fib(n)
    {
        let term = new Array(1000);
        term.fill(0);
 
        // base case
        if (n <= 1)
            return n;
 
        // if fib(n) has already
        // been computed we do not
        // do further recursive
        // calls and hence reduce
        // the number of repeated
        // work
        if (term[n] != 0)
            return term[n];
 
        else
        {
 
            // store the computed value
            // of fib(n) in an array
            // term at index n to so that
            // it does not needs to be
            // precomputed again
            term[n] = fib(n - 1) +
                      fib(n - 2);
 
            return term[n];
        }
    }
 
    let n = 6;
    document.write(fib(n));
     
    // This code is contributed by mukesh07.
</script>

8

Si el código recursivo se ha escrito una vez, entonces la memorización es simplemente modificar el programa recursivo y almacenar los valores devueltos para evitar llamadas repetitivas de funciones que se han calculado previamente.
 

Memoización 2-D
En el programa anterior, la función recursiva tenía solo un argumento cuyo valor no era constante después de cada llamada a la función. A continuación, se muestra una implementación donde el programa recursivo tiene dos argumentos no constantes. 
Por ejemplo, programa para resolver el problema estándar LCS Dynamic Problem cuando se dan dos strings. La solución recursiva general del problema es generar todas las subsecuencias de ambas secuencias dadas y encontrar la subsecuencia coincidente más larga. El total de combinaciones posibles será 2 ⁿ . Por lo tanto, la solución recursiva tomará O(2 ⁿ ) . El enfoque para escribir la solución recursiva se ha discutido aquí. 
A continuación se muestra la solución recursiva al problema LCS: 

// A Naive recursive implementation of LCS problem
#include <bits/stdc++.h>
 
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(char* X, char* Y, int m, int n)
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m - 1] == Y[n - 1])
        return 1 + lcs(X, Y, m - 1, n - 1);
    else
        return max(lcs(X, Y, m, n - 1),
                  lcs(X, Y, m - 1, n));
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
 
    int m = strlen(X);
    int n = strlen(Y);
 
    printf("Length of LCS is %dn", lcs(X, Y, m, n));
 
    return 0;
}

// A Naive recursive implementation of LCS problem
import java.io.*;
class GFG
{
 
    // Utility function to get max of 2 integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(String X, String Y, int m, int n)
    {
        if (m == 0 || n == 0)
            return 0;
        if (X.charAt(m - 1) == Y.charAt(n - 1))
            return 1 + lcs(X, Y, m - 1, n - 1);
        else
            return max(lcs(X, Y, m, n - 1),
                       lcs(X, Y, m - 1, n));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
 
        int m = X.length();
        int n = Y.length();
 
        System.out.print("Length of LCS is "
                         + lcs(X, Y, m, n));
    }
}
 
// This code is contributed by subhammahato348

# A Naive recursive implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n):
    if (m == 0 or n == 0):
        return 0;
    if (X[m - 1] == Y[n - 1]):
        return 1 + lcs(X, Y, m - 1, n - 1);
    else:
        return max(lcs(X, Y, m, n - 1),
                  lcs(X, Y, m - 1, n));
 
# Driver Code
if __name__=='__main__':
    X = "AGGTAB";
    Y = "GXTXAYB";
    m = len(X);
    n = len(Y);
    print("Length of LCS is {}n".format(lcs(X, Y, m, n)))
 
# This code is contributed by rutvik_56.

// A Naive recursive implementation of LCS problem
using System;
class GFG
{
 
  // Utility function to get max of 2 integers
  static int max(int a, int b) { return (a > b) ? a : b; }
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1]
  static int lcs(string X, string Y, int m, int n)
  {
    if (m == 0 || n == 0)
      return 0;
    if (X[m - 1] == Y[n - 1])
      return 1 + lcs(X, Y, m - 1, n - 1);
    else
      return max(lcs(X, Y, m, n - 1),
                 lcs(X, Y, m - 1, n));
  }
 
  // Driver Code
  public static void Main()
  {
    string X = "AGGTAB";
    string Y = "GXTXAYB";
 
    int m = X.Length;
    int n = Y.Length;
 
    Console.Write("Length of LCS is "
                  + lcs(X, Y, m, n));
  }
}
 
// This code is contributed by subhammahato348

<script>
// A Naive recursive implementation of LCS problem
 
    // Utility function to get max of 2 integers
    function max(a,b)
    {
         return (a > b) ? a : b;
    }
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    function lcs(X,Y,m,n)
    {
        if (m == 0 || n == 0)
            return 0;
        if (X[m-1] == Y[n-1])
            return 1 + lcs(X, Y, m - 1, n - 1);
        else
            return max(lcs(X, Y, m, n - 1),
                       lcs(X, Y, m - 1, n));
    }
     
    // Driver Code
    let X = "AGGTAB";
    let Y = "GXTXAYB";
    let m = X.length;
    let n = Y.length;
    document.write("Length of LCS is "
                         + lcs(X, Y, m, n));
     
     
 
// This code is contributed by avanitrachhadiya2155
</script>

Producción:

Length of LCS is 4

Teniendo en cuenta la implementación anterior, el siguiente es un árbol de recurrencia parcial para las strings de entrada «AXYT» y «AYZX» 
 

                  lcs("AXYT", "AYZX")
                       /                 \
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /           \                   /               \
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

En el árbol de recursión parcial anterior, lcs(“AXY”, “AYZ”) se resuelve dos veces . Al dibujar el árbol de recursión completo, se ha observado que hay muchos subproblemas que se resuelven una y otra vez. Por lo tanto, este problema tiene la propiedad de subestructura superpuesta y el recálculo de los mismos subproblemas se puede evitar mediante Memoización o Tabulación. El método de tabulación se ha discutido aquí.  
Un punto común de observación para usar la memorización en el código recursivo serán los dos argumentos no constantes M y N en cada llamada de función. La función tiene 4 argumentos, pero 2 argumentos son constantes, lo que no afecta la memorización. Las llamadas repetitivas ocurren para N y M que han sido llamados previamente. Entonces use una array 2-D para almacenar el cálculolcs(m, n) valor en arr[m-1][n-1] ya que el índice de string comienza desde 0. Cada vez que se vuelve a llamar a la función con el mismo argumento m y n, no realizamos ninguna otra llamada recursiva y devuelve arr[m-1][n-1] ya que el cálculo anterior de lcs(m, n) ya se almacenó en arr[m-1][n-1], lo que reduce las llamadas recursivas que ocurren más de una vez. 
A continuación se muestra la implementación del enfoque Memoization del código recursivo.  

// C++ program to memoize
// recursive implementation of LCS problem
#include <bits/stdc++.h>
int arr[1000][1000];
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
int lcs(char* X, char* Y, int m, int n)
{
    // base case
    if (m == 0 || n == 0)
        return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1] != -1)
        return arr[m - 1][n - 1];
 
    // if equal, then we store the value of the
    // function call
    if (X[m - 1] == Y[n - 1]) {
 
        // store it in arr to avoid further repetitive
        // work in future function calls
        arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
        return arr[m - 1][n - 1];
    }
    else {
        // store it in arr to avoid further repetitive
        // work in future function calls
        arr[m - 1][n - 1] = max(lcs(X, Y, m, n - 1),
                                lcs(X, Y, m - 1, n));
        return arr[m - 1][n - 1];
    }
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
    memset(arr, -1, sizeof(arr));
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
 
    int m = strlen(X);
    int n = strlen(Y);
 
    printf("Length of LCS is %d", lcs(X, Y, m, n));
 
    return 0;
}

// Java program to memoize
// recursive implementation of LCS problem
import java.io.*;
import java.lang.*;
class GFG
{
  public static int arr[][] = new int[1000][1000];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  public static int lcs(String X, String Y, int m, int n)
  {
 
    // base case
    if (m == 0 || n == 0)
      return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1] != -1)
      return arr[m - 1][n - 1];
 
    // if equal, then we store the value of the
    // function call
    if ( X.charAt(m - 1) == Y.charAt(n - 1))
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
      return arr[m - 1][n - 1];
    }
    else
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = max(lcs(X, Y, m, n - 1),
                              lcs(X, Y, m - 1, n));
      return arr[m - 1][n - 1];
    }
  }
 
  // Utility function to get max of 2 integers
  public static int max(int a, int b)
  {
    return (a > b) ? a : b;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    for(int i = 0; i < 1000; i++)
    {
      for(int j = 0; j < 1000; j++)
      {
        arr[i][j] = -1;
      }
    }
    String X = "AGGTAB";
    String Y = "GXTXAYB";
 
    int m = X.length();
    int n = Y.length();
 
    System.out.println("Length of LCS is " + lcs(X, Y, m, n));
  }
}
 
// This code is contributed by manupathria.

# Python3 program to memoize
# recursive implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
# memoization applied in recursive solution
def lcs(X, Y, m, n):
 
    global arr
 
    # base case
    if (m == 0 or n == 0):
        return 0
 
    # if the same state has already been
    # computed
    if (arr[m - 1][n - 1] != -1):
        return arr[m - 1][n - 1]
 
    # if equal, then we store the value of the
    # function call
    if (X[m - 1] == Y[n - 1]):
 
        # store it in arr to avoid further repetitive
        # work in future function calls
        arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1)
        return arr[m - 1][n - 1]
 
    else:
 
        # store it in arr to avoid further repetitive
        # work in future function calls
        arr[m - 1][n - 1] = max(lcs(X, Y, m, n - 1),
                                lcs(X, Y, m - 1, n))
        return arr[m - 1][n - 1]
 
 
# Driver code
 
arr = [[0]*1000]*1000
 
for i in range(0, 1000):
    for j in range(0, 1000):
        arr[i][j] = -1
 
X = "AGGTAB"
Y = "GXTXAYB"
 
m = len(X)
n = len(Y)
 
print("Length of LCS is ", lcs(X, Y, m, n))
 
# This code is contributed by Dharanendra L V.

// C# program to memoize
// recursive implementation of LCS problem
using System;
public class GFG
{
 
  public static int[, ] arr = new int[1000, 1000];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  public static int lcs(String X, String Y, int m, int n)
  {
 
    // base case
    if (m == 0 || n == 0)
      return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1, n - 1] != -1)
      return arr[m - 1, n - 1];
 
    // if equal, then we store the value of the
    // function call
    if ( X[m - 1] == Y[n - 1])
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1, n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
      return arr[m - 1, n - 1];
    }
    else
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1, n - 1] = max(lcs(X, Y, m, n - 1),
                              lcs(X, Y, m - 1, n));
      return arr[m - 1, n - 1];
    }
  }
 
  // Utility function to get max of 2 integers
  public static int max(int a, int b)
  {
    return (a > b) ? a : b;
  }
 
  // Driver code
  static public void Main (){
 
    for(int i = 0; i < 1000; i++)
    {
      for(int j = 0; j < 1000; j++)
      {
        arr[i, j] = -1;
      }
    }
    String X = "AGGTAB";
    String Y = "GXTXAYB";
 
    int m = X.Length;
    int n = Y.Length;
 
    Console.WriteLine("Length of LCS is " + lcs(X, Y, m, n));
  }
}
 
// This code is contributed by Dharanendra L V.

<script>
// Javascript program to memoize
// recursive implementation of LCS problem
     
    let arr=new Array(1000);
    for(let i=0;i<1000;i++)
    {
        arr[i]=new Array(1000);
        for(let j=0;j<1000;j++)
        {
            arr[i][j]=-1;
        }
    }
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
    function lcs(X,Y,m,n)
    {
        // base case
    if (m == 0 || n == 0)
      return 0;
  
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1] != -1)
        return arr[m - 1][n - 1];
  
    // if equal, then we store the value of the
    // function call
    if ( X[m-1] == Y[n-1])
    {
  
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
      return arr[m - 1][n - 1];
    }
    else
    {
  
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = Math.max(lcs(X, Y, m, n - 1),
                              lcs(X, Y, m - 1, n));
      return arr[m - 1][n - 1];
    }
    }
     
     
     
    // Driver code
    let X = "AGGTAB";
    let Y = "GXTXAYB";
    let m = X.length;
    let n = Y.length;
    document.write("Length of LCS is " + lcs(X, Y, m, n));
 
     
     
// This code is contributed by rag2127
</script>

Length of LCS is 4

Memoización 3-D

En el programa anterior, la función recursiva tenía solo dos argumentos cuyos valores no eran constantes después de cada llamada a la función. A continuación, se realiza una implementación donde el programa recursivo tiene tres argumentos no constantes . 
Por ejemplo, programa para resolver el problema estándar de Dynamic Problem LCS para tres strings. La solución recursiva general del problema es generar todas las subsecuencias de ambas secuencias dadas y encontrar la subsecuencia coincidente más larga. El total de combinaciones posibles será de 3 ⁿ . Por lo tanto, una solución recursiva tomará O(3 ⁿ ) . 
A continuación se muestra la solución recursiva al problema LCS:  

// A recursive implementation of LCS problem
// of three strings
#include <bits/stdc++.h>
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(char* X, char* Y, char* Z, int m, int n, int o)
{
    // base case
    if (m == 0 || n == 0 || o == 0)
        return 0;
 
    // if equal, then check for next combination
    if (X[m - 1] == Y[n - 1] and Y[n - 1] == Z[o - 1]) {
 
        // recursive call
        return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
    }
    else {
 
        // return the maximum of the three other
        // possible states in recursion
        return max(lcs(X, Y, Z, m, n - 1, o),
                   max(lcs(X, Y, Z, m - 1, n, o),
                       lcs(X, Y, Z, m, n, o - 1)));
    }
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
 
    char X[] = "geeks";
    char Y[] = "geeksfor";
    char Z[] = "geeksforge";
    int m = strlen(X);
    int n = strlen(Y);
    int o = strlen(Z);
    printf("Length of LCS is %d", lcs(X, Y, Z, m, n, o));
 
    return 0;
}

// A recursive implementation of LCS problem
// of three strings
class GFG
{
  // Utility function to get max of 2 integers
  static int max(int a, int b)
  {
    return (a > b) ? a : b;
  }
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1]
  static int lcs(char[] X, char[] Y, char[] Z,
                 int m, int n, int o)
  {
 
    // base case
    if (m == 0 || n == 0 || o == 0)
      return 0;
 
    // if equal, then check for next combination
    if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
    {
 
      // recursive call
      return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
    }
    else
    {
 
      // return the maximum of the three other
      // possible states in recursion
      return Math.max(lcs(X, Y, Z, m, n - 1, o),
                      Math.max(lcs(X, Y, Z, m - 1, n, o),
                               lcs(X, Y, Z, m, n, o - 1)));
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    char[] X = "geeks".toCharArray();
    char[] Y = "geeksfor".toCharArray();
    char[] Z = "geeksforge".toCharArray();
    int m = X.length;
    int n = Y.length;
    int o = Z.length;
    System.out.println("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by divyesh072019.

# A recursive implementation of LCS problem of three strings
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, Z, m, n, o):
    # base case
    if m == 0 or n == 0 or o == 0:
      return 5
     
    # if equal, then check for next combination
    if X[m - 1] == Y[n - 1] and Y[n - 1] == Z[o - 1]:
      # recursive call
      return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1)
    else:
      # return the maximum of the three other
      # possible states in recursion
      return max(lcs(X, Y, Z, m, n - 1, o), max(lcs(X, Y, Z, m - 1, n, o), lcs(X, Y, Z, m, n, o - 1)))
 
X = "geeks".split()
Y = "geeksfor".split()
Z = "geeksforge".split()
m = len(X)
n = len(Y)
o = len(Z)
print("Length of LCS is", lcs(X, Y, Z, m, n, o))
 
# This code is contributed by rameshtravel07.

// A recursive implementation of LCS problem
// of three strings
using System;
class GFG {
     
    // Utility function to get max of 2 integers
    static int max(int a, int b)
    {
        return (a > b) ? a : b;
    }
 
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(char[] X, char[] Y, char[] Z, int m, int n, int o)
    {
       
        // base case
        if (m == 0 || n == 0 || o == 0)
            return 0;
      
        // if equal, then check for next combination
        if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
        {
      
            // recursive call
            return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
        }
        else
        {
      
            // return the maximum of the three other
            // possible states in recursion
            return Math.Max(lcs(X, Y, Z, m, n - 1, o),
                       Math.Max(lcs(X, Y, Z, m - 1, n, o),
                           lcs(X, Y, Z, m, n, o - 1)));
        }
    }
 
  // Driver code
  static void Main()
  {
    char[] X = "geeks".ToCharArray();
    char[] Y = "geeksfor".ToCharArray();
    char[] Z = "geeksforge".ToCharArray();
    int m = X.Length;
    int n = Y.Length;
    int o = Z.Length;
    Console.WriteLine("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// A recursive implementation of LCS problem
// of three strings
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    function lcs(X,Y,Z,m,n,o)
    {
        // base case
    if (m == 0 || n == 0 || o == 0)
      return 0;
  
    // if equal, then check for next combination
    if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
    {
  
      // recursive call
      return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
    }
    else
    {
  
      // return the maximum of the three other
      // possible states in recursion
      return Math.max(lcs(X, Y, Z, m, n - 1, o),
                      Math.max(lcs(X, Y, Z, m - 1, n, o),
                               lcs(X, Y, Z, m, n, o - 1)));
    }
    }
     
    // Driver code
    let X = "geeks".split("");
    let Y = "geeksfor".split("");
    let Z = "geeksforge".split("");
    let m = X.length;
    let n = Y.length;
    let o = Z.length;
    document.write(
    "Length of LCS is " + lcs(X, Y, Z, m, n, o)
    );
     
 
// This code is contributed by unknown2108
 
</script>

Length of LCS is 5

El método de tabulación se ha mostrado aquí . Al dibujar el árbol de recurrencia por completo, se ha notado que hay muchos subproblemas superpuestos que se calculan varias veces. Dado que el parámetro de función tiene tres parámetros no constantes, se usará una array tridimensional para memorizar el valor que se devolvió cuando lcs(x, y, z, m, n, o) para cualquier valor de m, n, y o se llamó para que si lcs(x, y, z, m, n, o) se vuelve a llamar para el mismo valor de m, n, y o, entonces la función devolverá el valor ya almacenado como se calculó previamente en la llamada recursiva. arr[m][n][o] almacena el valor devuelto por el lcs(x, y, z, m, n, o)Llamada de función. La única modificación que debe realizarse en el programa recursivo es almacenar el valor de retorno del estado (m, n, o) de la función recursiva. El resto permanece igual en el programa recursivo anterior. 
A continuación se muestra la implementación del enfoque Memoization del código recursivo:  

// A memoize recursive implementation of LCS problem
#include <bits/stdc++.h>
int arr[100][100][100];
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
int lcs(char* X, char* Y, char* Z, int m, int n, int o)
{
    // base case
    if (m == 0 || n == 0 || o == 0)
        return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1][o - 1] != -1)
        return arr[m - 1][n - 1][o - 1];
 
    // if equal, then we store the value of the
    // function call
    if (X[m - 1] == Y[n - 1] and Y[n - 1] == Z[o - 1]) {
 
        // store it in arr to avoid further repetitive work
        // in future function calls
        arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                            n - 1, o - 1);
        return arr[m - 1][n - 1][o - 1];
    }
    else {
 
        // store it in arr to avoid further repetitive work
        // in future function calls
        arr[m - 1][n - 1][o - 1] =
                               max(lcs(X, Y, Z, m, n - 1, o),
                                 max(lcs(X, Y, Z, m - 1, n, o),
                                    lcs(X, Y, Z, m, n, o - 1)));
        return arr[m - 1][n - 1][o - 1];
    }
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
    memset(arr, -1, sizeof(arr));
    char X[] = "geeks";
    char Y[] = "geeksfor";
    char Z[] = "geeksforgeeks";
    int m = strlen(X);
    int n = strlen(Y);
    int o = strlen(Z);
    printf("Length of LCS is %d", lcs(X, Y, Z, m, n, o));
 
    return 0;
}

// A memoize recursive implementation of LCS problem
import java.io.*;
class GFG
{
   
  public static int[][][] arr = new int[100][100][100];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  static int lcs(String X, String Y, String Z,
                 int m, int n, int o)
  {
     
      // base case
      if (m == 0 || n == 0 || o == 0)
          return 0;
 
      // if the same state has already been
      // computed
      if (arr[m - 1][n - 1][o - 1] != -1)
          return arr[m - 1][n - 1][o - 1];
 
      // if equal, then we store the value of the
      // function call
      if (X.charAt(m - 1) == Y.charAt(n - 1) &&
          Y.charAt(n - 1) == Z.charAt(o - 1)) {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                              n - 1, o - 1);
          return arr[m - 1][n - 1][o - 1];
      }
      else
      {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] =
                                 max(lcs(X, Y, Z, m, n - 1, o),
                                   max(lcs(X, Y, Z, m - 1, n, o),
                                      lcs(X, Y, Z, m, n, o - 1)));
          return arr[m - 1][n - 1][o - 1];
      }
  }
 
  // Utility function to get max of 2 integers
  static int max(int a, int b)
  {
      return (a > b) ? a : b;
  }
 
  // Driver Code
  public static void main (String[] args)
  { 
    for(int i = 0; i < 100; i++)
    {
      for(int j = 0; j < 100; j++)
      {
        for(int k = 0; k < 100; k++)
        {
          arr[i][j][k] = -1;
        }
      }
    }
     
    String X = "geeks";
    String Y = "geeksfor";
    String Z = "geeksforgeeks";
    int m = X.length();
    int n = Y.length();
    int o = Z.length();
    System.out.print("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by Dharanendra L V.

# A memoize recursive implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1] */
# memoization applied in recursive solution
def lcs(X, Y, Z, m, n, o):
    global arr
 
    # base case
    if(m == 0 or n == 0 or o == 0):
        return 0
 
    # if the same state has already been
    # computed
    if (arr[m - 1][n - 1][o - 1] != -1):
        return arr[m - 1][n - 1][o - 1]
 
    # if equal, then we store the value of the
    # function call
    if (X[m - 1] == Y[n - 1] and
            Y[n - 1] == Z[o - 1]):
 
        # store it in arr to avoid further repetitive work
        # in future function calls
        arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                           n - 1, o - 1)
        return arr[m - 1][n - 1][o - 1]
 
    else:
 
        # store it in arr to avoid further repetitive work
        # in future function calls
        arr[m - 1][n - 1][o - 1] = max(lcs(X, Y, Z, m, n - 1, o),
                                       max(lcs(X, Y, Z, m - 1, n, o), lcs(X, Y, Z, m, n, o - 1)))
        return arr[m - 1][n - 1][o - 1]
 
# Driver Code
arr = [[[0 for k in range(100)] for j in range(100)] for i in range(100)]
 
for i in range(100):
    for j in range(100):
        for k in range(100):
            arr[i][j][k] = -1
 
X = "geeks"
Y = "geeksfor"
Z = "geeksforgeeks"
m = len(X)
n = len(Y)
o = len(Z)
print("Length of LCS is ", lcs(X, Y, Z, m, n, o))
 
# This code is contributed by Dharanendra L V.

// A memoize recursive implementation of LCS problem
using System;
public class GFG{
 
  public static int[, , ] arr = new int[100, 100, 100];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  static int lcs(String X, String Y, String Z, int m, int n, int o)
  {
      // base case
      if (m == 0 || n == 0 || o == 0)
          return 0;
 
      // if the same state has already been
      // computed
      if (arr[m - 1, n - 1, o - 1] != -1)
          return arr[m - 1, n - 1, o - 1];
 
      // if equal, then we store the value of the
      // function call
      if (X[m - 1] == Y[n - 1] &&
          Y[n - 1] == Z[o - 1]) {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1, n - 1, o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                              n - 1, o - 1);
          return arr[m - 1, n - 1, o - 1];
      }
      else {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1, n - 1, o - 1] =
                                 max(lcs(X, Y, Z, m, n - 1, o),
                                   max(lcs(X, Y, Z, m - 1, n, o),
                                      lcs(X, Y, Z, m, n, o - 1)));
          return arr[m - 1, n - 1, o - 1];
      }
  }
 
  // Utility function to get max of 2 integers
  static int max(int a, int b)
  {
      return (a > b) ? a : b;
  }
 
  // Driver Code
  static public void Main (){
 
    for(int i = 0; i < 100; i++) {
      for(int j = 0; j < 100; j++) {
        for(int k = 0; k < 100; k++) {
          arr[i, j, k] = -1;
        }
      }
    }
     
    String X = "geeks";
    String Y = "geeksfor";
    String Z = "geeksforgeeks";
    int m = X.Length;
    int n = Y.Length;
    int o = Z.Length;
    Console.WriteLine("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by Dharanendra L V.

<script>
// A memoize recursive implementation of LCS problem
     
    let arr=new Array(100);
    for(let i=0;i<100;i++)
    {
        arr[i]=new Array(100);
        for(let j=0;j<100;j++)
        {
            arr[i][j]=new Array(100);
            for(let k=0;k<100;k++)
            {
                arr[i][j][k]=-1;
            }
        }
    }
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
    function lcs(X,Y,Z,m,n,o)
    {
        // base case
      if (m == 0 || n == 0 || o == 0)
          return 0;
  
      // if the same state has already been
      // computed
      if (arr[m - 1][n - 1][o - 1] != -1)
          return arr[m - 1][n - 1][o - 1];
  
      // if equal, then we store the value of the
      // function call
      if (X[m-1] == Y[n-1] &&
          Y[n-1] == Z[o-1]) {
  
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                              n - 1, o - 1);
          return arr[m - 1][n - 1][o - 1];
      }
      else
      {
  
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] =
                                 max(lcs(X, Y, Z, m, n - 1, o),
                                   max(lcs(X, Y, Z, m - 1, n, o),
                                      lcs(X, Y, Z, m, n, o - 1)));
          return arr[m - 1][n - 1][o - 1];
      }
    }
     
    // Utility function to get max of 2 integers
    function max(a,b)
    {
         return (a > b) ? a : b;
    }
     
    // Driver Code
    let X = "geeks";
    let Y = "geeksfor";
    let Z = "geeksforgeeks";
    let m = X.length;
    let n = Y.length;
    let o = Z.length;
    document.write("Length of LCS is " + lcs(X, Y, Z, m, n, o));
     
     
 
 
// This code is contributed by patel2127
</script>

Length of LCS is 5

Nota: La array utilizada para Memoize se inicializa con algún valor (por ejemplo, -1) antes de la llamada de función para marcar si la función con los mismos parámetros se ha llamado previamente o no.