# Solve longest common subsequence in a non dynamic programming way? [closed]

I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I understand.

public class LCS
{
public static String lcs(String a, String b )
{
String lcs = lcs(a, b, "", 0, 0);
return lcs;
}
private static String lcs(String a, String b, String lcs, int i , int j)
{
int length_a = a.length();
int length_b = b.length();
if (i == length_a || j == length_b) return lcs;
if (a.charAt(i) == b.charAt(j))
{
lcs += a.charAt(i);
i++;
j++;
}
else
{
String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
String lcs_j_plus = lcs(a, b , lcs ,i, j+1);
if  ( lcs_i_plus.length() > lcs_j_plus.length())
i++;
else
j++;
}
return lcs(a, b, lcs , i, j) ;
}
public static void main(String[] args)
{
//client
String a = "GGCACCACG";
String b = "ACGGCGGATACG";
String lcs = lcs(a, b);
StdOut.println(lcs);
}
}


In contrast, the book I studied offered another solution which was claimed to solve the LCS problem via dynamic programming. The code looks as follows.

 public class LongestCommonSubsequence
{
public static String lcs(String s, String t)
{  // Compute length of LCS for all subproblems.
int m = s.length(), n = t.length();
int[][] opt = new int[m+1][n+1];
for (int i = m-1; i >= 0; i--)
for (int j = n-1; j >= 0; j--)
if (s.charAt(i) == t.charAt(j))
opt[i][j] = opt[i+1][j+1] + 1;
else
opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
// Recover LCS itself.
String lcs = "";
int i = 0, j = 0;
while(i < m && j < n)
{
if (s.charAt(i) == t.charAt(j))
{
lcs += s.charAt(i);
i++;
j++;
}
else if (opt[i+1][j] >= opt[i][j+1]) i++;
else                                 j++;
}
return lcs;
}
public static void main(String[] args)
{  StdOut.println(lcs(args, args));  }
}


I have tested both implementations and they produced the same results. My questions are:

1.Is my approach correct?

2.If my approach is correct, what are the time complexity of these two approaches?

• Unfortunately debugging your code is off-topic here. – Yuval Filmus Jul 18 '18 at 10:26
• @YuvalFilmus this is a legitimate question regarding the structure of dynamic programming. – koverman47 Jul 23 '18 at 22:42

2. The book's approach has a time complexity of $O(mn)$. Since your solution doesn't use memoization and recomputes the same results repeatedly, the time complexity is much worse. In fact, your approach is functionally equivalent to the brute force method, which has a time complexity of $O(2^n)$.
String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
String lcs_j_plus = lcs(a, b , lcs ,i, j+1);