dp经典题
题目
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).
Example
S> = “rabbbit”, T = “rabbit”Return 3.
解题思路
- 解法一:依次遍历两个字符串,直到T遍历结束,视为找到一个子串,这个就不用实现了
- 解法二:使用迭代思想,res表示T的第一个字符开始的子串能够找到子序列个数。将T的第一个字符依次和S中的字符比较,如果相同,则计算T的下一位子串和S的下一位子串,结果累加如res中。
解法一和解法二都存在重复计算问题,思路简单,但是大数据量时无法求解。 -
解法三:dp思想。
如果T[i] == S[j]则 dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1] 如果T[i] != S[j]则 dp[i][j] = dp[i][j + 1] 公式简单,程序更简单
-
解法四:类似于dp思想。数组dp[][] 第一维度表示T中第i个字符,第二维度表示上一个字符在S中开始找的位置,值表示T第i个可以在S第j位开始满足子串查找的个数。
写程序的时候感觉还行,现在想想感觉这个思路还是有点绕,用公式来理解的话比dp思路麻烦多了
程序
解法二
// 算法正确,递归不出来
public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
int res = 0;
if(T.length() == 0 || S.length()<T.length() )
return res;
char k = T.charAt(0);
if(T.length() == 1){
for(int i=0;i<S.length();i++){
if(k == S.charAt(i))
res = res + 1;
}
return res;
} else {
for(int i=0;i<=S.length()-T.length();i++){
if(k == S.charAt(i))
res = res + numDistinct(S.substring(i+1),T.substring(1));
}
return res;
}
}
}
解法三
public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
if (T.length() == 0 || S.length() < T.length())
return 0;
int[][] dp = new int[T.length() + 1][S.length() + 1];
Arrays.fill(dp[T.length()], 1);
for (int i = T.length() - 1; i >= 0; i--) {
for (int j = S.length() + i - T.length(); j >= 0; j--) {
if (S.charAt(j) == T.charAt(i))
dp[i][j] = dp[i][j + 1] + dp[i + 1][j + 1];
else
dp[i][j] = dp[i][j + 1];
}
}
return dp[0][0];
}
}
解法四
// 类dp解法
public class Solution {
/**
* @param S, T: Two string.
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
int res = 0;
if (T.length() == 0 || S.length() < T.length())
return res;
int[][] dp = new int[T.length()][S.length()];
for (int i = T.length() - 1; i >= 0; i--) {
for (int j = S.length() - 1; j >= 0; j--) {
if (i == T.length() - 1) {
if (S.charAt(j) == T.charAt(i))
dp[i][j] = 1;
} else {
if (S.charAt(j) == T.charAt(i)) {
int s = 0;
for (int k = j + 1; k < S.length(); k++)
s = s + dp[i + 1][k];
dp[i][j] = s;
}
}
}
}
int s = 0;
for (int i = 0; i < S.length(); i++)
s = s + dp[0][i];
return s;
}
}