Большинство задач динамического программирования решаются двумя способами:
- Таблица: Снизу Вверх
- Мемуаризация: Сверху Вниз
Один из более простых подходов к решению большинства проблем в DP состоит в том, чтобы сначала написать рекурсивный код, а затем написать метод табуляции снизу вверх или Запоминание рекурсивной функции сверху вниз. Шаги по написанию DP-решения нисходящего подхода к любой проблеме заключаются в том, чтобы:
- Напишите рекурсивный код
- Запомните возвращаемое значение и используйте его для уменьшения рекурсивных вызовов.
1-D Запоминание
Первым шагом будет написание рекурсивного кода. В приведенной ниже программе показана программа, связанная с рекурсией, в которой только один параметр изменяет свое значение. Поскольку только один параметр непостоянен, этот метод известен как 1-D запоминание. Например, задача ряда Фибоначчи для нахождения N-го члена в ряду Фибоначчи. Рекурсивный подход обсуждался здесь.
Ниже приведен рекурсивный код для нахождения N-го члена:
// 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Общим наблюдением является то, что эта реализация выполняет много повторяющейся работы (см. Следующее дерево рекурсии). Таким образом, это займет много времени для нахождения N-го числа Фибоначчи, если это будет сделано.
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 then once.Следующая проблема была решена с помощью Составление таблиц.
В приведенной ниже программе описаны шаги по написанию Программа подхода «сверху вниз». Некоторые изменения в рекурсивной программе позволят снизить сложность программы и дать желаемый результат. Если fib(x) не возникал ранее, то мы сохраняем значение fib(x) в термине массива с индексом x и возвращаемым термином[x]. Запоминая возвращаемое значение fib(x) в индексе x массива, уменьшите количество рекурсивных вызовов на следующем шаге, когда fib(x) уже был вызван. Таким образом, без дальнейших рекурсивных вызовов для вычисления значения fib(x), срок возврата[x] , когда fib(x) уже был вычислен ранее, чтобы избежать большой повторной работы, как показано в дереве.
Ниже приведен заученный рекурсивный код для поиска N-го термина.
// 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Если рекурсивный код был написан один раз, то запоминание-это просто модификация рекурсивной программы и сохранение возвращаемых значений, чтобы избежать повторяющихся вызовов функций, которые были вычислены ранее.
2-D Запоминание
В приведенной выше программе рекурсивная функция имела только один аргумент, значение которого не было постоянным после каждого вызова функции. Ниже показана реализация, в которой рекурсивная программа имеет два непостоянных аргумента.
Например, Программа для решения стандартной динамической задачи LCS, когда заданы две строки. Общее рекурсивное решение проблемы состоит в том, чтобы сгенерировать все подпоследовательности обеих заданных последовательностей и найти самую длинную совпадающую подпоследовательность. Всего возможных комбинаций будет 2н. Следовательно, рекурсивное решение займет O(2n). Подход к написанию рекурсивного решения обсуждался здесь.
Ниже приведено рекурсивное решение проблемы 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>
Выход:
Length of LCS is 4Учитывая приведенную выше реализацию, ниже приведено дерево частичной рекурсии для входных строк “AXYT” и “AYZX”
lcs("AXYT", "AYZX")
/ \
lcs("AXY", "AYZX") lcs("AXYT", "AYZ")
/ \ / \
lcs("AX", "AYZX") lcs("AXY", "AYZ") lcs("AXY", "AYZ") lcs("AXYT", "AY")В приведенном выше дереве частичной рекурсии lcs(“AXY”, “AYZ”) решается дважды. При построении полного дерева рекурсии было замечено, что существует множество подзадач, которые решаются снова и снова. Таким образом, эта проблема имеет свойство перекрывающейся подструктуры, и повторного вычисления одних и тех же подзадач можно избежать либо с помощью запоминания, либо с помощью таблиц. Метод составления таблиц обсуждался здесь.
Общей точкой наблюдения для использования запоминания в рекурсивном коде будут два непостоянных аргумента M и N в каждом вызове функции. Функция имеет 4 аргумента, но 2 аргумента являются постоянными, что не влияет на запоминание. Повторяющиеся вызовы выполняются для N и M, которые были вызваны ранее. Поэтому используйте массив 2-D для хранения вычисленного значения lcs(m, n) в arr[m-1][n-1], так как строковый индекс начинается с 0. Всякий раз, когда функция с тем же аргументом m и n вызывается снова, мы не выполняем никаких дальнейших рекурсивных вызовов и возвращаем arr[m-1][n-1], поскольку предыдущее вычисление lcs(m, n) уже было сохранено в arr[m-1][n-1], следовательно, сокращая рекурсивные вызовы, которые происходят несколько раз.
Ниже приведена реализация подхода запоминания рекурсивного кода.
// 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 43-D Запоминание
В приведенной выше программе рекурсивная функция имела только два аргумента, значения которых не были постоянными после каждого вызова функции. Ниже приведена реализация, в которой рекурсивная программа имеет три непостоянных аргумента.
Например, Программа для решения стандартной динамической задачи LCS для трех строк. Общее рекурсивное решение проблемы состоит в том, чтобы сгенерировать все подпоследовательности обеих заданных последовательностей и найти самую длинную совпадающую подпоследовательность. Общее количество возможных комбинаций составит 3n. Следовательно, рекурсивное решение займет O(3n).
Ниже приведено рекурсивное решение проблемы 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Был показан метод табуляции здесь. При полном построении дерева рекурсии было замечено, что существует множество перекрывающихся подзадач, которые вычисляются несколько раз. Поскольку параметр функции имеет три непостоянных параметра, следовательно, для запоминания значения, возвращенного при lcs(x, y, z, m, n, o) для любого значения m, n и o было вызвано так, что если lcs(x, y, z, m, n, o) снова вызывается для того же значения m, n и o, затем функция вернет уже сохраненное значение, как оно было вычислено ранее в рекурсивном вызове. arr[m][n][o] хранит значение, возвращенное lcs(x, y, z, m, n, o). Единственное изменение, которое необходимо выполнить в рекурсивной программе, — это сохранить возвращаемое значение (m, n, o) состояния рекурсивной функции. Остальное остается неизменным в вышеупомянутой рекурсивной программе.
Ниже приведена реализация подхода запоминания рекурсивного кода:
// 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Примечание: Массив, используемый для запоминания, инициализируется до некоторого значения (скажем, -1) перед вызовом функции, чтобы отметить, была ли ранее вызвана функция с теми же параметрами или нет.
