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.
解法三：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;
}
}
