leetcode原题，

动态规划

dp[i][j] 代表 T 前 i 字符串可以由 S 前j 字符串组成最多个数.

所以动态方程:

当 S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];（前T的前i-1个由S的前j-1个组成的个数，与T的前i个被S的前j-1个组成的个数，dp[i][j-1]有点类似于不选s[j]能凑成t[1..i]的个数，相反dp[i-1][j-1]则为选s[j]能凑成t[1...i]的个数。）

当 S[j] != T[i] , dp[i][j] = dp[i][j-1]（不想等，只能不选s[j]）

需要注意的是，初始化的时候，因为空集是所有字符串子集, 所以我们第一行都是 1

不过这题有点鬼，我数组开1e4*1e4就RA，开1000*1000反而AC了，有点不太懂

#define inf 0x3f3f3f3f
#define MAX 1005
#define ll long long
#define vec vector<int>
#define P pair<int,int>
#define MOD 1000000007

int main() {
	ll dp[MAX][MAX];
	int T; cin >> T;
	while (T--) {
		string s, t;
		cin >> s >> t;
		s = ' ' + s, t = ' ' + t;
		int l1 = s.size(), l2 = t.size();
		for (int i = 1; i < l2; i++)for (int j = 1; j < l1; j++)dp[i][j] = 0;
		for (int i = 0; i < s.size(); i++)dp[0][i] = 1;
		for (int i = 1; i < t.size(); i++) {
			for (int j = i; j < s.size(); j++) {
				if (t[i] =...