public static int lengthofLongestCommonSubsequenceOtherWayDPTB(String input1, String input2) {
int index1 = 0, index2 = 0, currentLength = 0;
Integer[][] dp = new Integer[input1.length()][input2.length()];
int length = lengthofLongestCommonSubsequenceOtherWayDPTB(input1.toCharArray(), input2.toCharArray(), index1, index2,
currentLength, dp);
return length;
}
private static int lengthofLongestCommonSubsequenceOtherWayDPTB(char[] input1, char[] input2, int index1,
int index2, int currentLength, Integer[][] dp) {
if (index1 >= input1.length) {
return currentLength;
}
if (index2 >= input2.length) {
return currentLength;
}
if (dp[index1][index2] != null) {
return dp[index1][index2];
}
if (input1[index1] == input2[index2]) {
dp[index1][index2] =lengthofLongestCommonSubsequenceOtherWayDPTB(input1, input2, index1 + 1, index2 + 1, currentLength+1, dp);
}
else {
dp[index1][index2] = max(lengthofLongestCommonSubsequenceOtherWayDPTB(input1, input2, index1, index2 + 1, currentLength, dp),
lengthofLongestCommonSubsequenceOtherWayDPTB(input1, input2, index1 + 1, index2, currentLength, dp));
}
return dp[index1][index2];
}