class Solution { public: /** * * @param S string字符串 * @param T string字符串 * @return int整型 */ int numDistinct(string S, string T) { int m = T.length(); int n = S.length(); int **dp = new int*[m+1]; //动态规划表 for(int i = 0;i<m+1;i++) { dp[i] = new int[n+1]; //给二元组开空间 } for(int j = 0;j<n;j++) { dp[0][j] = 1; //为dp的第一行进行初始化 } for(int i = 1;i<m+1;i++) { for(int j=1;j<n+1;j++) { if(S[j-1]==T[i-1])//当子串和母串的字母符合时,将该元素左边和左上的元素加起来 dp[i][j] = dp[i-1][j-1]+dp[i][j-1]; else dp[i][j] = dp[i][j-1]; } } return dp[m][n]; } };