Solve longest common subsequence in a non dynamic programming way? 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() &gt; 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 &gt;= 0; i--)
       for (int j = n-1; j &gt;= 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 &lt; m &amp;&amp; j &lt; n)
    {
       if (s.charAt(i) == t.charAt(j))
       {
          lcs += s.charAt(i);
          i++;
          j++;
       }
       else if (opt[i+1][j] &gt;= opt[i][j+1]) i++;
       else                                 j++;
    }
       return lcs; 
    }
    public static void main(String[] args)
    {  StdOut.println(lcs(args[0], args[1]));  }
}


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?
Your approach is correct in the sense that you produce the correct results.

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)$.


Note that with

String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
String lcs_j_plus = lcs(a, b , lcs ,i, j+1);

You recompute a subset of the problem on every single iteration without saving any of the results. The purpose of memoization is to save the results of the sub problems (so you don't have to recompute them) and then use those results to construct a solution to your original problem.