- 原题：https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=3&rp=3&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
- 思路：
- 这个题目一般看起来都会是一个动态规划算法的题目，因为想要得到最终子序列的种类就需要先得到 S的子序列中有多少可行的序列，然后子序列的子序列中有多少可行的序列，这个就可以转换为DP算法求解。
- 这里需要考虑我们需要维护什么样的变量来记录可行序列的种类。这里我们定义一个dp[m][n]二维数组，用来表示S中前m个 T中前n个字符对应的可行的序列个数。从小到大的方式进行存储。i=1，j=1，dp[0][0] = 1;这里对第一列上面所有数字设为1,（因为当t为空的时候，永远都是只有一种方法变为空串）；然后第一行全为0，因为当S为空，肯定是不行的，所以为0.
动态规划一般的方法都是利用二维数组来进行每一层的计算（特殊处理方式都是在第一行第一列），最终得出对角线上的数值。 - 我们从第一个字符开始进行比较。如果S[i-1] == T[j-1],那么表示dp[i][j] = dp[i-1][j-1] + dp[i-1][j];这个意思是两个字符相同的话，我们可以将他们舍去也可以将他们保留，这样的话前面的dp[i-1][j-1]中序列称为了新的序列，再加上dp[i-1][j]的序列，所以总的序列就是这个值
- 如果S[i-1] != T[j-1] 那么说明dp[i][j] = dp[i-1][j]；这个意思是如果两个字符不同的话，那么我们就该舍弃，那么对应的就等于dp[i-1][j],前面该是多少是多少，i,j加入进来不会增加任何的变化。
- 实例图
- 代码
class Solution { public: int numDistinct(string S, string T) { int length_s = S.length(); int length_t = T.length(); //m行n列：行表示S，列表示T：dp数组用来存储S的前i T的前j个字符可以有多少个可行的序列。 vector < vector<int> > dp(length_s+1, vector<int>(length_t+1, 0)); dp[0][0] = 1; //这个表示任意的一个字符串变成空串只有一种方法 for (int i=0; i<length_s+1; i++){ dp[i][0] = 1; } //从第一个个字符开始依次进行比较， //如果找到相同的字符那么这个字符可以保留也可以舍去 公式：dp[i][j] = dp[i-1][j-1] + dp[i-1][j] //如果不相同的话，那么这个序列就是不行的了，所以就是直接等于dp[i][j] = dp[i-1][j] for (int i=1; i<length_s+1; i++){ for (int j=1; j<length_t+1; j++){ if (S[i-1] == T[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; else dp[i][j] = dp[i-1][j]; } } return dp[length_s][length_t]; } };