題目
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).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
解題之法
class Solution {
public:
int numDistinct(string S, string T) {
int dp[T.size() + 1][S.size() + 1];
for (int i = 0; i <= S.size(); ++i) dp[0][i] = 1;
for (int i = 1; i <= T.size(); ++i) dp[i][0] = 0;
for (int i = 1; i <= T.size(); ++i) {
for (int j = 1; j <= S.size(); ++j) {
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0);
}
}
return dp[T.size()][S.size()];
}
};
分析
給定兩個字符串S和T蕉堰，求S有多少個不同的子串與T相同典蝌。S的子串定義為在S中任意去掉0個或者多個字符形成的串误甚。
看到有關(guān)字符串的子序列或者配準類的問題，首先應該考慮的就是用動態(tài)規(guī)劃Dynamic Programming來求解，這個應成為條件反射。而所有DP問題的核心就是找出遞推公式，像這道題就是遞推一個二維的dp數(shù)組甲捏，下面我們從題目中給的例子來分析，這個二維dp數(shù)組應為：
? r a b b b i t
? 1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
首先鞭执，若原字符串和子序列都為空時摊鸡，返回1绽媒，因為空串也是空串的一個子序列。
若原字符串不為空免猾，而子序列為空是辕，也返回1，因為空串也是任意字符串的一個子序列猎提。
而當原字符串為空获三，子序列不為空時，返回0锨苏，因為非空字符串不能當空字符串的子序列疙教。
理清這些，二維數(shù)組dp的邊緣便可以初始化了伞租，下面只要找出遞推式贞谓，就可以更新整個dp數(shù)組了。我們通過觀察上面的二維數(shù)組可以發(fā)現(xiàn)葵诈，當更新到dp[i][j]時裸弦，dp[i][j] >= dp[i][j - 1] 總是成立，再進一步觀察發(fā)現(xiàn)作喘，當 T[i - 1] == S[j - 1] 時理疙，dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]，若不等泞坦， dp[i][j] = dp[i][j - 1]窖贤，所以，綜合以上贰锁，遞推式為：
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)
