來源：
LeetCode第115題
難度：
困難
問題描述
給定一個字符串S和一個字符串t，計算在S的子序列中t出現的個數。
注解：
字符串的一個子序列是指，通過刪除一些(也可以不刪除)字符且不干擾剩余字符的相對位置所組成的新字符串(例如，"ACE"是"ABCDE"的一個子序列，而"AEC"不是)，題目數據保證答案符合32位帶符號整數范圍。
示例：
輸入：s="rabbbit",t="rabbit"
輸出：有三種可以從s中獲得"rabbit"的方案：rabbbit、rabbbit、rabbbit
動態規劃解決
對于這種A和B子串的題目，多使用動態規劃來進行解決，我們使用dp[i][j]表示t的前i個字符串可以由s的前j個字符組成的個數,最終求出dp[tLength][sLength]即可(tLength和sLength)分別表示t和s的長度：
?
public int numTinS(String T,String S)//子串T作為第一個參數，母串S作為第二個參數
{
//求解子串和母串的長度用于生成動態規劃數組dp[][]
int TLength=T.length();
int SLength=S.length();
//生成動態規劃數組
int dp[][]=new int[TLength][SLength];
//動態數組的第一項工作就是初始化，對于二維dp數組，常需要初始化dp[0][0]、dp[i][0]、dp[0][j]
//初始化dp[0][0],也就是子串T的第一個字符(下標為0)與母串S的第一個字符是否相等
if(T.charAt(0)==S.charAt(0))
{
dp[0][0]=1;
}else
{
dp[0][0]=0;
}
//初始化dp[0][i]也就是子串的第一個字母在母串S中的出現次數
for(int i=1;i<SLength;i++)
{
if(T.charAt(0)==S.charAt(i))
{
dp[0][i]=dp[0][i-1]+1;
}else
{
dp[0][i]=dp[0][i-1];
}
}
//初始化dp[j][0],由于全部子串不可能比母串長，從而都是0
for(int i=1;i<TLength;i++)
{
dp[i][0]=0;
}for(int i=1;i<TLength;i++)
{
for(int j=1;j<SLength;j++)
{
if(T.charAt(i)==S.charAt(j))
{
//如果i和j相同，那么可以由子串的前i個字符在母串的j-1個字符中的個數dp[i][j-1]加上
//子串前i-1個字符在母串的j-1個字符的個數，第i和第j已經對應
dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
}else
{
dp[i][j]=dp[i][j-1];
}
}
}
return dp[TLength-1][SLenhgth-1];
}總結：求解數組的長度用String.length()方法，申請二維數組使用int dp[][]=new int [length1][length2];在求解兩個數組問題時要想到動態規劃。
)
