面试题95：
问题：
输入两个字符串，求出它们的最长公共子序列的长度。
解决方案：
- 因为这个题目没有要求求出所有公共子序列，只是要求计算最长公共子序列，也就是求题目的最优解，故使用动态规划来解决。
- 因为输入有两个字符串，因此状态转移方程有两个参数。用函数f（i，j）表示第1个字符串中下标从0到i的子字符串（记为s1[0…i]）和第2个字符串中下标从0到j的子字符串（记为s2[0…j]）的最长公共子序列的长度。
- 如果第一个字符串中下标为i的字符与第二个字符串中下标为j的字符相同时，那么f（i，j）相当于在s1[0…i-1]和s2[0…j-1]的最长公共子序列的后面添加一个公共字符，也就是f（i，j）=f（i-1，j-1）+1。如果第一个字符串中下标为i的字符与第二个字符串中下标为j的字符不相同时，那么f（i，j）相当于在s1[0…i]和s2[0…j-1]或s1[0…i-1]和s2[0…j]的最长公共子序列，也就是f（i，j）= max（f（i-1，j），f（i，j-1））。
- 当状态转移方程的i或j等于0时，即求f（0，j）或f（i，0）时可能需要f（-1，j）或f（i，-1）的值。f（0，j）的含义是s1[0…0]和s2[0…j]这两个子字符串的最长公共子序列的长度，即第1个子字符串只包含一个下标为0的字符，那么f（-1，j）对应的第1个子字符串再减少一个字符，所以第1个子字符串是空字符串。任意空字符串和另一个字符串的公共子序列的长度都是0，所f（-1，j）的值等于0。同理，f（i，-1）的值也等于0。
源代码：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
//因为数组没有-1下标，故将数组的长度加1，数组原来的下标0位置让给下标-1，模拟-1下标
int[][] dp = new int[len1+1][len2+1];
for(int i = -1;i < len1;i++){
for(int j = -1;j < len2;j++){
int one = i + 1;
int two = j + 1;
if(i == -1 || j == -1){
//任意空字符串和另一个字符串的公共子序列的长度都是0
dp[one][two] = 0;
}else{
char ch1 = text1.charAt(i);
char ch2 = text2.charAt(j);
//第一个字符串中下标为i的字符与第二个字符串中下标为j的字符相同时，那么在dp（i-1，j-1）的最长公共子序列的后面添加一个公共字符
if(ch1 == ch2){
dp[one][two] = dp[i][j] + 1;
//第一个字符串中下标为i的字符与第二个字符串中下标为j的字符不相同时，那么在dp（i-1，j）或dp（i，j-1）的最长公共子序列的最大值
}else{
dp[one][two] = Math.max(dp[one][j],dp[i][two]);
}
}
}
}
return dp[len1][len2];
}
}
优化空间效率思路：
观察上述代码，我们可以发现f（i，j）的值依赖于f（i-1，j-1）或f（i-1，j）、f（i，j-1），因此实际上我们只需要保存数组的两行就可以了。
源代码：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
int[][] dp = new int[2][len2 + 1];
for(int i = -1;i < len1;i++){
for(int j = -1;j < len2;j++){
int one = i + 1;
int two = j + 1;
if(i == -1 || j == -1){
dp[one % 2][two] = 0;
}else{
char ch1 = text1.charAt(i);
char ch2 = text2.charAt(j);
if(ch1 == ch2){
dp[one % 2][two] = dp[i % 2][j] + 1;
}else{
dp[one % 2][two] = Math.max(dp[one % 2][j],dp[i % 2][two]);
}
}
}
}
return dp[len1 % 2][len2];
}
}
优化空间效率思路：
观察上述代码，我们可以发现f（i，j）的值依赖于f（i-1，j-1）或f（i-1，j）、f（i，j-1），我们将 f（i-1，j）都保存在数组dp下标j+1的位置，f（i，j-1）就是f（j-1），f（i-1，j-1）用临时变量prev保存，将二维数组压缩为一维数组。
源代码：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
if(len1 < len2){
longestCommonSubsequence(text2,text1);
}
int[] dp = new int[len2+1];
for(int i = 0;i < len1;i++){
//prev保存f（i-1，j-1）
int prev = dp[0];
for(int j = 0;j < len2;j++){
int cur;
//第一个字符串中下标为i的字符与第二个字符串中下标为j的字符相同时，因为prev保存f（i-1，j-1），那么只需要在f（i-1，j-1）的基础上加一，也就是prev + 1
if(text1.charAt(i) == text2.charAt(j)){
cur = prev + 1;
//第一个字符串中下标为i的字符与第二个字符串中下标为j的字符不相同时，因为dp[j]保存的是f（i，j-1），dp[j+1]保存的是f（i-1，j），故只需要求它们的最大值。
}else{
cur = Math.max(dp[j],dp[j+1]);
}
//因为dp[j+1]保存的是f（i-1，j），将它保存到prev，因为下一步就要计算f（i，j+1）需要用到f（i-1，j）
prev = dp[j+1];
dp[j+1] = cur;
}
}
return dp[len2];
}
}
面试题96：
问题：
输入3个字符串s1、s2、s3，判断字符串s3能不能由字符串s1、s2交织而成。
解决方案：
- 因为题目没有要求列出求字符串s1和s2交织成s3的方法，只是让我们判断字符串s3能不能由字符串s1、s2交织而成，故使用动态规划。
- 如果字符串s1的长度为m，字符串s2的长度为n，用函数f（i，j）表示字符串s1的下标从0到i的子字符串（记为s1[0…i]，长度为i+1）和字符串s2的下标从0到j的子字符串（记为s2[0…j]，长度为j+1）能否交织得到字符串s3的下标从0到i+j+1（记为s3[0…i+j+1]，长度为i+j+2）的子字符串。f（m-1，n-1）就是问题的解。
- 字符串s3的下标为i+j+1的字符，既可能来自字符串s1的下标i的字符，又可能来自字符串s2的下标j的字符。如果s3的下标为i+j+1的字符与字符串s1的下标i的字符相同，那么f（i，j） = f（i-1，j）的值；如果s3的下标为i+j+1的字符与字符串s2的下标j的字符相同，那么f（i，j） = f（i，j-1）的值。
- 当状态转移方程的i或j等于0时，即求f（0，j）或f（i，0）时可能需要f（-1，j）或f（i，-1）的值。f（-1，j）的含义是当前字符串s1的子字符串为空，它和字符串s2从下标0到j的子字符串能不能交织成字符串s3中下标从0到j的子字符串，f（i，-1）同理。
源代码：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if(len1 + len2 != len3){
return false;
}
boolean[][] dp = new boolean[len1+1][len2+1];
dp[0][0] = true;
//当字符串s2的子字符串为空时，它和字符串s1从下标0到i的子字符串能不能交织成字符串s3中下标从0到i的子字符串
for(int i = 0;i < len1;i++){
dp[i+1][0] = s1.charAt(i) == s3.charAt(i) && dp[i][0];
}
//当字符串s1的子字符串为空时，它和字符串s2从下标0到j的子字符串能不能交织成字符串s3中下标从0到j的子字符串
for(int j = 0;j < len2;j++){
dp[0][j+1] = s2.charAt(j) == s3.charAt(j) && dp[0][j];
}
//当字符串s1和字符串s2都不为空时，它们的子字符串能不能交织成字符串s3中下标从0到i+j+1的子字符串
for(int i = 0;i < len1;i++){
for(int j = 0;j < len2;j++){
char ch1 = s1.charAt(i);
char ch2 = s2.charAt(j);
char ch3 = s3.charAt(i+j+1);
dp[i+1][j+1] = (ch1 == ch3 && dp[i][j+1]) || (ch2 == ch3 && dp[i+1][j]);
}
}
return dp[len1][len2];
}
}
优化空间效率思路：
观察上述代码，可以发现f（i，j）依赖于f（i-1，j）、f（i，j-1），f（i-1，j）的值在计算出f（i，j）之后就不再需要，因此可以用同一个位置保存f（i-1，j）和f（i，j）的值。该位置在f（i，j）计算之前保存的是f（i-1，j）的值，而f（i，j-1）在计算f（i，j）之前就已经计算好了。
源代码：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if(len1 + len2 != len3){
return false;
}
if(len1 < len2){
return isInterleave(s2,s1,s3);
}
boolean[] dp = new boolean[len2 + 1];
dp[0] = true;
for(int j = 0;j < len2;j++){
dp[j+1] = s2.charAt(j) == s3.charAt(j) && dp[j];
}
for(int i = 0;i < len1;i++){
dp[0] = dp[0] && s1.charAt(i) == s3.charAt(i);
for(int j = 0;j < len2;j++){
char ch1 = s1.charAt(i);
char ch2 = s2.charAt(j);
char ch3 = s3.charAt(i + j + 1);
//括号里面的dp[j+1]由于还没有完成f（i，j）的计算，因此此时“dp[j+1]”中保存的还是f（i-1，j）的值。
dp[j+1] = (ch1 == ch3 && dp[j+1]) || (ch2 == ch3 && dp[j]);
}
}
return dp[len2];
}
}
面试题97：
问题：
输入字符串S和T，请计算字符串S中有多少个子序列等于字符串T。
解决方案：
- 用f（i，j）表示字符串S下标从0到i的子字符串（记为S[0…i]）中等于字符串T下标从0到j的子字符串（记为T[0…j]）的子序列的数目。如果字符串S的长度是m，字符串T的长度是n，那么f（m-1，n-1）就是字符串S中等于字符串T的子序列的数目。
- 如果字符串S中下标为i的字符（记为S[i]）等于字符串T中下标为j的字符（记为T[j]），那么对S[i]有两个选择：一个是用S[i]去匹配T[j]，那么S[0…i]中等于T[0…j]的子序列的数目等于S[0…i-1]中等于T[0…j-1]的子序列的数目；另一个是舍去S[i]，那么S[0…i]中等于T[0…j]的子序列的数目等于S[0…i-1]中等于T[0…j]的子序列的数目。因此，当S[i]等于T[j]时，f（i，j）等于f（i-1，j-1）+f（i-1，j）。如果S[i]和T[j]不相同，则只能舍去S[i]，此时f（i，j）等于f（i-1，j）。
- 当字符串S、T都为空时，两个字符串匹配，因此f（-1，-1）等于1。如果字符串S为空而字符串T不为空，那么字符串S中不可能存在等于字符串T的子序列，即当j大于或等于0时f（-1，j）等于0。如果字符串S为不为空而字符串T为空，那么f（i，-1）等于1。
源代码：
class Solution {
public int numDistinct(String s, String t) {
int lenS = s.length();
int lenT = t.length();
if(lenS < lenT){
return 0;
}
int[][] dp = new int[lenS+1][lenT+1];
//字符串S、T都为空时，f（-1，-1）等于1
dp[0][0] = 1;
for(int i = 0;i < lenS;i++){
//字符串S为不为空而字符串T为空，那么f（i，-1）等于1
dp[i+1][0] = 1;
for(int j = 0;j <= i && j < lenT;j++){
if(s.charAt(i) == t.charAt(j)){
dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
}else{
dp[i+1][j+1] = dp[i][j+1];
}
}
}
return dp[lenS][lenT];
}
}
