怎样做百度网站,个人小程序,湖南岳阳网站,能找本地人做导游的网站目录动态规划题目来源 115. 不同的子序列
动态规划
1.确定dp数组#xff08;dp table#xff09;以及下标的含义
dp[i][j]#xff1a;以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.确定递推公式
这一类问题#xff0c;基本是要分析两种情况 t[i - 1…
目录动态规划题目来源 115. 不同的子序列
动态规划
1.确定dp数组dp table以及下标的含义
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.确定递推公式
这一类问题基本是要分析两种情况 t[i - 1] 与 s[j - 1]相等 t[i - 1] 与 s[j - 1] 不相等 当t[i - 1] 与 s[j - 1]相等时dp[i][j]可以有两部分组成。 一部分是用t[i - 1]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要 dp[i-1][j-1]。 一部分是不用s[j - 1]来匹配个数为dp[i][j-1]。
例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。 当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。 所以当t[i - 1] 与 s[j - 1]相等时dp[i][j] dp[i - 1][j - 1] dp[i ][j-1];
当t[i - 1] 与 s[j - 1]不相等时dp[i][j]只有一部分组成不用s[j - 1]来匹配就是模拟在s中删除这个元素即dp[i][j-1] 所以递推公式为dp[i][j] dp[i][j-1];
为什么只考虑 不用s[j - 1]来匹配 这种情况 不考虑 不用t[i - 1]来匹配 的情况呢。 我们求的是 s 中有多少个 t而不是 求t中有多少个s所以只考虑 s中删除元素的情况即 不用t[i - 1]来匹配 的情况。
3.dp数组如何初始化
从递推公式dp[i][j] dp[i - 1][j - 1] dp[i][j-1]; 和 dp[i][j] dp[i][j-1]; 中可以看出dp[i][j] 是从左方和左上方推导而来那么 dp[i][0] 和dp[0][j]是一定要初始化的。
dp[0][j] 表示以j-1为结尾的s可以随便删除元素出现空字符串的个数。 那么dp[i][0]一定都是0s如论如何也变成不了t。
4.确定遍历顺序
从递推公式dp[i][j] dp[i - 1][j - 1] dp[i ][j-1]; 和 dp[i][j] dp[i ][j-1]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。 所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
5.举例推导dp数组
S “babgbag”, T “bag” 推导dp数组状态如下 代码实现
class Solution {public int numDistinct(String s, String t) {int[][] dp new int[t.length()1][s.length()1];for(int i 0;is.length();i){dp[0][i] 1;}for(int i1;it.length();i){for(int j 1;js.length();j){if(t.charAt(i-1) s.charAt(j-1)){dp[i][j] dp[i-1][j-1] dp[i][j-1];}else{dp[i][j] dp[i][j-1];}}}return dp[t.length()][s.length()];}
}
