Hemos discutido los subproblemas superpuestos y las propiedades de la subestructura óptima en el conjunto 1 y el conjunto 2, respectivamente. También discutimos un problema de ejemplo en el Conjunto 3 . Analicemos el problema de la subsecuencia común más larga (LCS) como un problema de ejemplo más que se puede resolver mediante la programación dinámica.
Declaración del problema de LCS: dadas dos secuencias, encuentre la longitud de la subsecuencia más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua. Por ejemplo, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc son subsecuencias de “abcdefg”.
C++
/* A Naive recursive implementation of LCS problem */
#include <bits/stdc++.h>
using namespace std;
/* 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));
}
/* Driver code */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;
return 0;
}
// This code is contributed by rathbhupendra
C
/* 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 program to test above function */
int main()
{
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
/* A Naive recursive implementation of LCS problem in java*/
public class LongestCommonSubsequence
{
/* 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;
}
public static void main(String[] args)
{
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is" + " " +
lcs.lcs( X, Y, m, n ) );
}
}
// This Code is Contributed by Saket Kumar
Python3
# A Naive recursive Python implementation of LCS problem
def lcs(X, Y, m, n):
if m == 0 or n == 0:
return 0
elif 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 program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print ("Length of LCS is ", lcs(X , Y, len(X), len(Y)) )
C#
/* C# Naive recursive implementation of LCS problem */
using System;
class GFG
{
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
static 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 */
static int max(int a, int b)
{
return (a > b)? a : b;
}
public static void Main()
{
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X=s1.ToCharArray();
char[] Y=s2.ToCharArray();
int m = X.Length;
int n = Y.Length;
Console.Write("Length of LCS is" + " "
+lcs( X, Y, m, n ) );
}
}
// This code is Contributed by Sam007
PHP
<?php
// A Naive recursive PHP
// implementation of LCS problem
function lcs($X, $Y, $m, $n)
{
if($m == 0 || $n == 0)
return 0;
else 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
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of LCS is ";
echo lcs($X , $Y, strlen($X),
strlen($Y));
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
/* A Naive recursive implementation of LCS problem in java*/
/* 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));
}
/* Utility function to get max of 2 integers */
function max(a , b)
{
return (a > b)? a : b;
}
var s1 = "AGGTAB";
var s2 = "GXTXAYB";
var X=s1;
var Y=s2;
var m = X.length;
var n = Y.length;
document.write("Length of LCS is" + " " +
lcs( X, Y, m, n ) );
// This code contributed by umadevi9616
</script>
C++
/* A Top-Down DP implementation of LCS problem */
#include <bits/stdc++.h>
using namespace std;
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(char* X, char* Y, int m, int n,
vector<vector<int> >& dp)
{
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);
if (dp[m][n] != -1) {
return dp[m][n];
}
return dp[m][n] = max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp));
}
/* Driver code */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
vector<vector<int> > dp(m + 1, vector<int>(n + 1, -1));
cout << "Length of LCS is " << lcs(X, Y, m, n, dp);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// A Top-Down DP implementation of LCS problem
// Returns length of LCS for X[0..m-1], Y[0..n-1]
static int lcs(String X,String Y,int m,int n,int[][] dp){
if (m == 0 || n == 0)
return 0;
if (dp[m][n] != -1)
return dp[m][n];
if(X.charAt(m - 1) == Y.charAt(n - 1)){
dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);
return dp[m][n];
}
dp[m][n] = Math.max(lcs(X, Y, m, n - 1, dp),lcs(X, Y, m - 1, n, dp));
return dp[m][n];
}
// Drivers code
public static void main(String args[]){
String X = "AGGTAB";
String Y = "GXTXAYB";
int m = X.length();
int n = Y.length();
int[][] dp = new int[m + 1][n + 1];
for(int i=0;i<m + 1;i++){
for(int j=0;j<n + 1;j++){
dp[i][j] = -1;
}
}
System.out.println("Length of LCS is "+lcs(X, Y, m, n, dp));
}
}
// This code is contributed by shinjanpatra
Python3
# A Top-Down DP implementation of LCS problem
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n, dp):
if (m == 0 or n == 0):
return 0
if (dp[m][n] != -1):
return dp[m][n]
if X[m - 1] == Y[n - 1]:
dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp)
return dp[m][n]
dp[m][n] = max(lcs(X, Y, m, n - 1, dp),lcs(X, Y, m - 1, n, dp))
return dp[m][n]
# Driver code
X = "AGGTAB"
Y = "GXTXAYB"
m = len(X)
n = len(Y)
dp = [[-1 for i in range(n + 1)]for j in range(m + 1)]
print(f"Length of LCS is {lcs(X, Y, m, n, dp)}")
# This code is contributed by shinjanpatra
C#
/* C# Naive recursive implementation of LCS problem */
using System;
class GFG {
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
static int lcs(char[] X, char[] Y, int m, int n, int [,]L) {
if (m == 0 || n == 0)
return 0;
if (L[m, n] != -1)
return L[m, n];
if (X[m - 1] == Y[n - 1]) {
L[m, n] = 1 + lcs(X, Y, m - 1, n - 1, L);
return L[m, n];
}
L[m, n] = max(lcs(X, Y, m, n - 1, L), lcs(X, Y, m - 1, n, L));
return L[m, n];
}
/* Utility function to get max of 2 integers */
static int max(int a, int b) {
return (a > b) ? a : b;
}
public static void Main() {
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X = s1.ToCharArray();
char[] Y = s2.ToCharArray();
int m = X.Length;
int n = Y.Length;
int[,]L = new int[m + 1, n + 1];
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
L[i, j] = -1;
}
}
Console.Write("Length of LCS is" + " "
+ lcs(X, Y, m, n, L));
}
}
// This code is contrributed by akshitsaxenaa09
Javascript
<script>
/* A Top-Down DP implementation of LCS problem */
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
function lcs(X, Y, m, n, dp)
{
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);
if (dp[m][n] != -1) {
return dp[m][n];
}
return dp[m][n] = Math.max(lcs(X, Y, m, n - 1, dp),
lcs(X, Y, m - 1, n, dp));
}
/* Driver code */
let X = "AGGTAB";
let Y = "GXTXAYB";
let m = X.length;
let n = Y.length;
let dp = new Array(m + 1);
for(let i = 0; i < m + 1; i++)
{
dp[i] = new Array(n + 1).fill(-1);
}
document.write("Length of LCS is " + lcs(X, Y, m, n, dp));
// This code is contributed by shinjanpatra
</script>
Python3
def lcs(s1 , s2):
m, n = len(s1), len(s2)
prev, cur = [0]*(n+1), [0]*(n+1)
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
cur[j] = 1 + prev[j-1]
else:
if cur[j-1] > prev[j]:
cur[j] = cur[j-1]
else:
cur[j] = prev[j]
cur, prev = prev, cur
return prev[n]
#end of function lcs
# Driver program to test the above function
s1 = "AGGTAB"
s2 = "GXTXAYB"
print("Length of LCS is ", lcs(s1, s2))
# BY PRASHANT SHEKHAR MISHRA
C++
/* Dynamic Programming C implementation of LCS problem */
#include <bits/stdc++.h>
using namespace std;
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(char *X, char *Y, int m, int n)
{
// intitalizing a matrix of size (m+1)*(n+1)
int L[m + 1][n + 1];
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
// L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]
return L[m][n];
}
// Driver program to test above function
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
cout << "Length of LCS is: " << lcs(X, Y, m, n);
return 0;
}
// code submitted by Aditya Yadav (adityayadav012552)
Java
/* Dynamic Programming Java implementation of LCS problem */
public class LongestCommonSubsequence
{
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char[] X, char[] Y, int m, int n )
{
int L[][] = new int[m+1][n+1];
/* Following steps build L[m+1][n+1] in bottom up fashion. Note
that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i-1] == Y[j-1])
L[i][j] = L[i-1][j-1] + 1;
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b)? a : b;
}
public static void main(String[] args)
{
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is" + " " +
lcs.lcs( X, Y, m, n ) );
}
}
// This Code is Contributed by Saket Kumar
Python3
# Dynamic Programming implementation of LCS problem
def lcs(X , Y):
# find the length of the strings
m = len(X)
n = len(Y)
# declaring the array for storing the dp values
L = [[None]*(n+1) for i in range(m+1)]
"""Following steps build L[m+1][n+1] in bottom up fashion
Note: L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-1]"""
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0 :
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j] , L[i][j-1])
# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
return L[m][n]
#end of function lcs
# Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print ("Length of LCS is ", lcs(X, Y) )
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// Dynamic Programming C# implementation
// of LCS problem
using System;
class GFG
{
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
static int lcs( char[] X, char[] Y, int m, int n )
{
int [,]L = new int[m+1,n+1];
/* Following steps build L[m+1][n+1]
in bottom up fashion. Note
that L[i][j] contains length of
LCS of X[0..i-1] and Y[0..j-1] */
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i, j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i, j] = L[i - 1, j - 1] + 1;
else
L[i, j] = max(L[i - 1, j], L[i, j - 1]);
}
}
return L[m, n];
}
/* 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 s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X=s1.ToCharArray();
char[] Y=s2.ToCharArray();
int m = X.Length;
int n = Y.Length;
Console.Write("Length of LCS is" + " " +lcs( X, Y, m, n ) );
}
}
// This Code is Contributed by Sam007
PHP
<?php
// Dynamic Programming C#
// implementation of LCS problem
function lcs($X , $Y)
{
// find the length of the strings
$m = strlen($X);
$n = strlen($Y) ;
// declaring the array for
// storing the dp values
/*Following steps build L[m+1][n+1]
in bottom up fashion .
Note: L[i][j] contains length of
LCS of X[0..i-1] and Y[0..j-1] */
for ($i = 0; $i <= $m; $i++)
{
for ($j = 0; $j <= $n; $j++)
{
if ($i == 0 || $j == 0)
$L[$i][$j] = 0;
else if ($X[$i - 1] == $Y[$j - 1])
$L[$i][$j] = $L[$i - 1][$j - 1] + 1;
else
$L[$i][$j] = max($L[$i - 1][$j],
$L[$i][$j - 1]);
}
}
// L[m][n] contains the length of
// LCS of X[0..n-1] & Y[0..m-1]
return $L[$m][$n];
}
// Driver Code
$X = "AGGTAB";
$Y = "GXTXAYB";
echo "Length of LCS is ";
echo lcs($X, $Y);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// Dynamic Programming Java implementation of LCS problem
// Utility function to get max of 2 integers
function max(a, b)
{
if (a > b)
return a;
else
return b;
}
// Returns length of LCS for X[0..m-1], Y[0..n-1]
function lcs(X, Y, m, n)
{
var L = new Array(m + 1);
for(var i = 0; i < L.length; i++)
{
L[i] = new Array(n + 1);
}
var i, j;
/* Following steps build L[m+1][n+1] in
bottom up fashion. Note that L[i][j]
contains length of LCS of X[0..i-1]
and Y[0..j-1] */
for(i = 0; i <= m; i++)
{
for(j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
/* L[m][n] contains length of LCS
for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
// Driver code
var x = "AGGTAB";
var y = "GXTXAYB";
var m = x.length;
var n = y.length;
document.write("Length of LCS is " + lcs(x, y, m, n));
// This code is contributed by akshitsaxenaa09
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA