package algorithms.dp;

public class LongestCommonSubsequence {

  public int lcs(String s1, String s2) {
    return lcs(s1, s2, s1.length(), s2.length());
  }

  private int lcs(String s1, String s2, int i, int j) {
    if (i == 0 || j == 0) {
      return 0;
    } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
      return lcs(s1, s2, i - 1, j - 1) + 1;
    } else {
      return Math.max(lcs(s1, s2, i, j - 1), lcs(s1, s2, i - 1, j));
    }
  }

  public int lcsTabulated(String s1, String s2) {
    int[][] table = new int[s1.length() + 1][s2.length() + 1];

    for (int i = 1; i < table.length; i++) {
      for (int j = 1; j < table[0].length; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          table[i][j] = table[i - 1][j - 1] + 1;
        } else {
          table[i][j] = Math.max(table[i][j - 1], table[i - 1][j]);
        }
      }
    }

    return table[s1.length()][s2.length()];
  }

  public static void main(String[] args) {
    LongestCommonSubsequence lcs = new LongestCommonSubsequence();
    System.out.println(lcs.lcsTabulated("Aerodrone", "Airpod"));
    System.out.println(lcs.lcsTabulated("AGGRTAB", "GXTXAYB"));
  }
}

@@ -911,24 +911,673 @@
 th()%5D;%0A  %7D%0A%0A
+  public int lcsMemoized(String s1, String s2) %7B%0A    return lcsMemoized(s1, s2, s1.length(), s2.length(), new int%5Bs1.length()%5D%5Bs2.length()%5D);%0A  %7D%0A%0A  private int lcsMemoized(String s1, String s2, int i, int j, int%5B%5D%5B%5D results) %7B%0A    if (i == 0 %7C%7C j == 0) %7B%0A      return 0;%0A    %7D%0A%0A    if (results%5Bi - 1%5D%5Bj - 1%5D == 0) %7B%0A      if (s1.charAt(i - 1) == s2.charAt(j - 1)) %7B%0A        results%5Bi - 1%5D%5Bj - 1%5D = lcsMemoized(s1, s2, i - 1, j - 1, results) + 1;%0A      %7D else %7B%0A        results%5Bi - 1%5D%5Bj - 1%5D = Math.max(lcsMemoized(s1, s2, i, j - 1, results),%0A            lcsMemoized(s1, s2, i - 1, j, results));%0A      %7D%0A    %7D%0A    return results%5Bi - 1%5D%5Bj - 1%5D;%0A  %7D%0A%0A
   public sta
@@ -1728,14 +1728,44 @@
 rone
-%22, %22Ai
+AerodroneAerodrone%22, %22AirpodAiAirpod
 rpod
@@ -1769,24 +1769,26 @@
 pod%22));%0A    
+//
 System.out.p
@@ -1831,18 +1831,112 @@
 GXTXAYB%22));%0A
+    System.out.println(lcs.lcsMemoized(%22AerodroneAerodroneAerodrone%22, %22AirpodAiAirpodrpod%22));%0A
   %7D%0A%7D%0A

Add memoized solution as well