代码随想录打卡第55天|392.判断子序列；115.不同的子序列

392.判断子序列

关键点1：dp数组的含义

dp[i][j]是以i-1,j-1为结尾的最长公共子序列的长度；

关键点2：递归公式的推导

 if(nums1[i-1] == nums2[j-1])，则i和j同时移动，所以为i-1,j-1；dp[i][j] = dp[i-1][j-1]+1;

如果不相等：则i不退，j往前退一步，因为j是长的那个序列，i是短的子序列是不需要退的，只需要退j来判断是否与i相等

关键点3：dp数组初始化

每个dp[i][j]元素都初始化为0，因为dp[0][j] =dp[-1][j-1]+1; ,dp[i][0] = dp[i-1][-1]+1;都出现了无意义的dp[-1]，所以dp[0][j] 和 dp[i][0] 都初始化为0 ，而其它元素也可初始化为0，所以整个数组初始化为0；

关键点4：遍历顺序

由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（0已经初始化，且为使递归公式的dp[i-1][j-1]有意义，i,j都从1开始遍历）。

关键点5：最终判断

如果最长公共子序列的长度等于子序列s的长度 if(dp[s.length()][t.length()] == s.length())，则返回true。

class Solution {public boolean isSubsequence(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];for(int i = 1; i <= s.length();i++){for(int j = 1;j <= t.length();j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = dp[i][j-1];}}}if(dp[s.length()][t.length()] == s.length()){return true;}else{return false;}}
}

115.不同的子序列 

关键点1：dp数组的含义

 dp[i][j]表示从0-i-1,0-j-1的s字符串中字符串t出现的次数

关键点2：递归公式的推导

2-1：i-1与j-1相等：有两种情况

情况1：使用i-1与j-1相等，则i-2与j-2相等的次数就是i-1与j-1相等的次数，不加1 的原因是这里是出现的次数，而不是求公共长度；

情况2：不使用i-1与j-1相等，则将i（长序列的索引）往前走一位，再判断两个字符串的第i-2位与j-1位是否相等

2-2：i-1与j-1不相等

i往前退一步，j不退，因为i是长的那个序列，j是短的子序列是不需要退的，只需要退i来判断是否与j相等

关键点3：dp数组初始化

需要对最左边那列和最上面那行进行初始化

dp[0][j] = dp[-1][j-1]：表示长字符串是空，短字符串不是空的情况下，长字符串中短字符串出现的次数，所以初始化为0

dp[i][0] = dp[i-1][-1]：表示长字符串不是空，短字符串是空的情况下，长字符串中短字符串出现的次数，所以初始化为1，长字符串将元素全部删除就是空串了

而其它元素可初始化为0；

关键点4：遍历顺序

由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（0已经初始化，且为使递归公式的dp[i-1][j-1]有意义，i,j都从1开始遍历）。

class Solution {public int numDistinct(String s, String t) {// dp[i][j]表示从0-i-1,0-j-1的s字符串中字符串t出现的次数int[][] dp = new int[s.length()+1][t.length()+1];// 初始化dp数组for(int i = 0; i <= s.length();i++){dp[i][0] = 1;}for(int i = 1; i <= s.length();i++){for(int j = 1; j <= t.length();j++){if(s.charAt(i-1) == t.charAt(j-1)){// i-1与j-1相等时有两种情况// 情况1：使用i-1与j-1相等，则i-2与j-2相等的次数就是i-1与j-1相等的次数// 情况2：不使用i-1与j-1相等，则将s序列往前走一位，再判断两个字符串的第i-2位与j-1位是否相等dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{// 不相等的情况：将s序列往前走一位，再判断两个字符串的第i-2位与j-1位是否相等dp[i][j] = dp[i-1][j];}}}return dp[s.length()][t.length()];}
}