张家港做网站排名,网站建设能赚很多钱,马尾福州网站建设,wordpress自动加链接392.判断子序列 动规五部曲#xff1a;
确定dp数组#xff08;dp table#xff09;以及下标的含义 dp[i][j] 表示以下标i-1为结尾的字符串s#xff0c;和以下标j-1为结尾的字符串t#xff0c;相同子序列的长度为dp[i][j]。确定递推公式 在确定递推公式的时候#xff0c;…392.判断子序列 动规五部曲
确定dp数组dp table以及下标的含义 dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。确定递推公式 在确定递推公式的时候首先要考虑如下两种操作整理如下 if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了 if (s[i - 1] ! t[j - 1]) 相当于t要删除元素继续匹配dp数组如何初始化 从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]所以dp[0][0]和dp[i][0]是一定要初始化的。 4.确定遍历顺序 同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]那么遍历顺序也应该是从上到下从左到右模拟递归
class Solution {public boolean isSubsequence(String s, String t) {int[][] dpnew int[s.length()1][t.length()1];for(int i1;is.length();i){for(int j1;jt.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];}}}return dp[s.length()][t.length()]s.length();}
}115.不同的子序列 确定dp数组dp table以及下标的含义 dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。确定递推公式 这一类问题基本是要分析两种情况 -s[i - 1] 与 t[j - 1]相等 s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时dp[i][j]可以有两部分组成。 一部分是用s[i - 1]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要 dp[i-1][j-1]。 一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。 所以当s[i - 1] 与 t[j - 1]相等时dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];当s[i - 1] 与 t[j - 1]不相等时dp[i][j]只有一部分组成不用s[i - 1]来匹配就是模拟在s中删除这个元素即dp[i - 1][j] 所以递推公式为dp[i][j] dp[i - 1][j];
dp数组如何初始化 从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来如图那么 dp[i][0] 和dp[0][j]是一定要初始化的。
dp[i][0]一定都是1因为也就是把以i-1为结尾的s删除所有元素出现空字符串的个数就是1。
确定遍历顺序 从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。举例推导dp数组
class Solution {public int numDistinct(String s, String t) {int[][] dpnew int[s.length()1][t.length()1];for(int i0;is.length();i){dp[i][0]1;}for(int i1;is.length()1;i){for(int j1;jt.length()1;j){if(s.charAt(i-1)t.charAt(j-1)){dp[i][j]dp[i-1][j-1]dp[i-1][j];}else{dp[i][j]dp[i-1][j];}}}return dp[s.length()][t.length()];}
}
