[数据结构与算法]字符串如何求给定子序列的数量（动态规划求解）

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

假设 S=”rabbbit“ ，T=”rabbit“

下面是图例

• 最终结果是dp[T.size()][S.size()]
• 每当T[i] == S[j]时， dp[i][j]会增加， 比如S?= rabb, T?= rab. 此时dp[i][j] = dp[i][j-1] + x （x为增加量）
• 当T[i] != S[j]时 dp[i][j] 会不变
• x是什么呢?，对于例子S=rabbb， T=rabb, x为2， 而dp[i-1][j-1] = 2, 而且其他的例子也能推出来，所以可以假设x = dp[i-1][j-1]
• 当计算dp[i][j]时， dp[i][j-1]是一定被包括进去的， 当两个字符串的最后一个字符相同时， 那么dp[i-1][j-1]也会包括进去

递推式：dp[i][j] = dp[i][j - 1] + (t[i] == s[j]) ?dp[i - 1][j - 1] : 0

而且通过上面的例子 可以找到初始情况

dp[0][j] = 0;
dp[j][0] = 1; (包含空串)
dp[0][0] = 1 （防止第一个条件覆盖）

#include<bits/stdc++.h>
using namespace std;



int main(){
	string s, t;
	while(cin >> s >> t){
		//给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数
		//求s中有多少个t（子序列）
		//t的长度为dp数组的横坐标长度，s的长度为dp数组中纵坐标的长度 
		vector<vector<int> > dp(t.length() + 5, vector<int>(s.length() + 5, 0));
		for(int i = 0; i < t.length() + 1; i++){
			dp[0][i] = 1;
		}
		for(int l = 0; l < s.length() + 1; l++){
			dp[l][0] = 0;
		}
		dp[0][0] = 1;
		for(int i = 1; i < t.length() + 1; i++){
			for(int l = 1; l < s.length() + 1; l++){
				dp[i][l] = dp[i][l - 1];
				if(t[i - 1] == s[l - 1]){
					dp[i][l] += dp[i - 1][l - 1];
				}
			}
		}
		cout << dp[t.length()][s.length()] << endl;
	}
	return 0;
}