本文主要是介绍代码随想录算法训练营day58 || 392. 判断子序列115. 不同的子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划，用相似思路解决复杂问题 | LeetCode：392.判断子序列_哔哩哔哩_bilibili
动态规划之子序列，为了编辑距离做铺垫 | LeetCode：115.不同的子序列_哔哩哔哩_bilibili
392. 判断子序列
思目，两个字符串中可以任意删除字符塑造公共的子序列。本题的递推方程在元素相等时dp[i][j] = dp[i-1][j-1]+1；两者不等路：序列题时是dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])；初做本题时，对不等时候的递推公式可以理解是：i位置与j位置不等，那么直接继承i-1位置或j-1位置的上一次状态；因为可能i-1位置与j位置相等；i位置与j-1位置可能相等；或者所有情况皆不成立的话，也是对从前向后递推所形成的状态的继承。而站在 编辑距离 的角度来看，这个dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])的操作就是删除i位置元素或删除j位置元素，从而求取两个字符串的共同序列。
// 时间复杂度O(n^2)
// 空间复杂度O(n^2)class Solution {public boolean isSubsequence(String s, String t) {int n = s.length();int m = t.length();// dp数组的含义是s下标i与t的下标j之间的公共子序列的长度是多少，这里的子序列是不连续的若干字符int[][] dp = new int[n+1][m+1];// 遍历顺序从前向后，初始化是dp[0][0] = 0for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1]+1;}elsedp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // 这一步表示既可以删除s当前i位置的字符，也可以删除t的j位置的字符，从而直接关联上一个位置的状态}}if(dp[n][m] == s.length())return true;return false; }
}115. 不同的子序列
思路：当s的i位置的元素与t的j位置的元素相等时，s可以与t一起往前推一个位置（这个操作是当前i位置与j位置分别在各自字符串中是唯一的，或者说题目中所要判断的仅仅是两个字符串是否存在共同子序列，所以纵使s中有重复的元素，但是不会影响判断结果；共同字串的话就不行）；也可以s不选当前的位置，即此时dp[i][j]表示的是s的i位置前与t的j位置前，不同的子序列个数有几个；因此s不选当前的位置，即类似于两者不是合适的匹配元素，要找其他的元素，所以此时是要延续上一状态dp[i-1][j]，这里是在s中找有几个t，所以只会由s来判断当前t位置的元素我是否选择，所以仅仅是dp[i-1][j]，而不考虑dp[i][j-1]；因此s的i位置与t的j位置相等时，有两个状态转移来源，所以需要对两个状态进行相加。
不等时，按照相等时不选择的状态延续操作，赋值dp[i-1][j]即可。
如果站在编辑距离的角度来看，dp[i-1][j]也是单向的删除操作，即只会删除s而不会删除t内的元素，删除的元素，就是重复出现的元素。
// 时间复杂度O(n^2)
// 空间复杂度O(n^2)class Solution {public int numDistinct(String s, String t) {if(s.length() < t.length())return 0;int n = s.length();int m = t.length();int[][] dp = new int[n+1][m+1];for(int i=0; i<=n; i++)dp[i][0] = 1;// 从前往后推没有初始化，从后往前时需要考虑t为空串，dp[i][m] = 1for(int i=1; i<=n ;i++){for(int j=1; j<=m; j++){if(s.charAt(i-1) == t.charAt(j-1))dp[i][j] = dp[i-1][j-1]+dp[i-1][j]; // 补上si不与tj比较，而是选择与j位置前的元素比较，因此关联上j-1之前元素所形成的状态dp[i-1][j]elsedp[i][j] = dp[i-1][j];}}return dp[n][m];// 滚动数组的优化做法不太理解// int[] dp = new int[m+1];// dp[0] = 1;// // 从前往后推没有初始化，从后往前时需要考虑t为空串，dp[i][m] = 1// for(int i=1; i<=n ;i++){// for(int j=m; j>0; j--){// if(s.charAt(i-1) == t.charAt(j-1))// dp[j] += dp[j-1]; // 补上si不与tj比较，而是选择与j位置前的元素比较，因此关联上j-1之前元素所形成的状态dp[i-1][j]// }// }// return dp[m];}
}这篇关于代码随想录算法训练营day58 || 392. 判断子序列115. 不同的子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
