0
$\begingroup$

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[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?

$\endgroup$

closed as off-topic by Evil, Discrete lizard, Yuval Filmus, David Richerby, Kyle Jones Jul 25 '18 at 3:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – Evil, Discrete lizard, Yuval Filmus, David Richerby, Kyle Jones
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Unfortunately debugging your code is off-topic here. $\endgroup$ – Yuval Filmus Jul 18 '18 at 10:26
  • $\begingroup$ @YuvalFilmus this is a legitimate question regarding the structure of dynamic programming. $\endgroup$ – koverman47 Jul 23 '18 at 22:42
0
$\begingroup$
  1. Your approach is correct in the sense that you produce the correct results.

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

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.