本文共 1232 字，大约阅读时间需要 4 分钟。

思路：

这个问题让人联想到最长公共子序列的问题，因此可以用动态规划的问题来解决。最难的部分在于状态迁移的实际含义，这点好推出来，却很难理解。

和最长公共子序列的问题一样，用dp[i][j]的数组来表示状态，含义为在s中取i个字符，在t中取j个字符，s中i个字符能够得到多少个t中j个字符组成的序列。很明显当j大于i时，结果一定为0。当j等于0时，结果一定为1。这就是边界条件了。

同时注意到，当i大于j时（其实大不大于无关紧要，只是为了好理解一些），无论i的最后一个字符是什么，dp[i][j]都至少要等于dp[i-1][j]，因为s延长了，解不可能比s更短时还要小。例如s=“abc%”，t="abc"，则无论%代表什么，解的数量至少为s="abc"，t="abc"的解。可以直观认识到，当%不等于‘c’时，其实两种情况解数量是相等的。

关键点在于%等于‘c’时怎么办？怎么表示‘净’多出来的解的数量？

我的理解是：首先看待继承自dp[i-1][j]的那部分解数时，不考虑%，也就是说%“一定不“参与匹配，无论%代表c还是不是c。等到考虑净多出来的部分时，%”一定“参与匹配，我们可以将t中的最后一个字符和%”固定“匹配起来，这样净多出来的数量应该是dp[i-1][j-1]。从集合的角度来讲”一定不“和”一定“两种情况没有交集，并且并集为全集。

这样得到递推式dp[i][j] = dp[i-1][j] (s[i-1]!=t[j-1])和dp[i][j] = dp[i-1][j] + dp[i-1][j-1] (s[i-1]==t[i-1])

int numDistinct(string s, string t) {	int m = s.size();	int n = t.size();		int* * dp = new int*[m+1];	for (int i = 0; i < m + 1;i++){		dp[i] = new int[n + 1]{0};	}	for (int i = 0; i < m + 1;i++){		dp[i][0] = 1;//任何串到""都是1种情况	}	for (int i = 0; i < m + 1;i++){		for (int j = 1; j < n + 1;j++){			if (j>i){				dp[i][j] = 0;				continue;			}			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];			}		}	}	int result = dp[m][n];	for (int i = 0; i < m + 1;i++){		delete[] dp[i];	}	delete[] dp;	return result;}

转载地址：http://ubdii.baihongyu.com/