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()
解法三
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;
}
}