前言：
在之前的LDU训练赛和UPC训练赛中都出现了字串包含问题，在我前面的两篇博客中也介绍了那两个题的思路，但是这两个题有一个共同的特点，那就是他们要寻找的字串都是提前已知的，如果给出任意两个串，寻找A串中B字串的个数，之前我的思路显然不可用，因此我找到了力扣的“不同的子序列”这个问题，进行学习；
题目描述：
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
来源：力扣（LeetCode）
链接：不同的子序列
提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
思路：
这题我们用动态规划来做
1.当s.length<t.lenth 时不存在子序列
2.当s.length>=t.lenth 时
设二维数组dp[ i ][ j ] 表示 s[ :i ] 中 字串 t[ :j ] 出现的个数
s[ :i ]表示 s 串从 0 到 i 的部分
t[ :j ] 表示 t 串 从0 到 j 的部分
我们首先进行预处理：
当 j = 0 时，s串无论取任意长度，空串都是它的字串
for(int i=0;i<=lena;i++) dp[i][0]=1;
当 i = 0 时 t串无论取任意长度，s不可能含有字串
for(int i=1;i<=lenb;i++) dp[0][i]=0;
特别注意 dp[ 0 ][ 0 ] = 1;
不要在第二次赋值时把这个值覆盖掉；
1.当s[ i ] = t[ j ] 时
s[ i ] 自己可以选择自己是否与 t[ j ] 匹配
若s[ i ] 与 t[ j ]匹配 那么考虑 t[ :j -1] 做 s[ :i-1 ] 的字串
dp[ i ][ j ] =dp[ i -1][ j-1 ]
若s[ i ] 与 t[ j ]不匹配 那么考虑 t[ :j ] 做 s[ :i-1 ]的字串
dp[ i ][ j ] =dp[ i -1][ j ]
2.当s[ i ] ！= t[ j ] 时
s[ i ] 不可以于 t[ j ] 匹配
那么考虑 t[ :j ] 做 s[ :i-1 ]的字串
dp[ i ][ j ] =dp[ i -1][ j ]
因此转移方程：
for(int i=1;i<=lena;i++) { for(int j=1;j<=lenb;j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j]; else dp[i][j]=dp[i-1][j]; } }
最终代码：
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e5+100; const int p = 1e4; const double eps = 1e-8; string a,b; ull dp[1000][1000];// a[:i]子序列中 b[:j]子序列出现的次数 int lena,lenb; int main() { cin>>a; cin>>b; lena=a.size(); lenb=b.size(); if(lena<lenb) { cout<<"0"; retrun 0; } for(int i=0;i<=lena;i++) dp[i][0]=1; for(int i=1;i<=lenb;i++) dp[0][i]=0; for(int i=1;i<=lena;i++) { for(int j=1;j<=lenb;j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j]; else dp[i][j]=dp[i-1][j]; } } cout<<dp[lena][lenb]; }
数据加强版：
如果仅仅是一个动态规划没什么意思，但是如果这个题加强一下数据变成
0 <= s.length, t.length <= 2000，那么我想即使是 unsigned long long 也放不下最终的结果，这时候就需要高精度的帮助
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e5+100; const int p = 1e4; const double eps = 1e-8; string a,b; string dp[2000][2000];// a[:i]子序列中 b[:j]子序列出现的次数 int lena,lenb; string add(string s1,string s2) { int len1=s1.size(); int len2=s2.size(); string ss=""; int a[N],b[N]; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=0;i<len1;i++) a[i+1]=s1[len1-1-i]-'0'; for(int i=0;i<len2;i++) b[i+1]=s2[len2-1-i]-'0'; int l=1,r=1,k=1,carry=0; while(l<=len1||r<=len2) { b[k]=a[l]+b[r]+carry; carry=b[k]/10; b[k]%=10; l++;r++;k++; } while(carry) { b[k]=carry%10; carry/=10; k++; } for(int i=k-1;i>=1;i--) ss+=(b[i]+'0'); return ss; } int main() { cin>>a; cin>>b; lena=a.size(); lenb=b.size(); if(lena<lenb) { cout<<"0"; retrun 0; } for(int i=0;i<=lena;i++) dp[i][0]="1"; for(int i=1;i<=lenb;i++) dp[0][i]="0"; for(int i=1;i<=lena;i++) { for(int j=1;j<=lenb;j++) { if(a[i-1]==b[j-1]) dp[i][j]=add(dp[i-1][j-1],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } } cout<<dp[lena][lenb]; }
注意：易出错的地方在于高精的时候存入数组处理后是倒序的，所以放到一个新串中要倒着处理，而且用两个数组处理高精而不用三个，节省时间空间不易爆内存
之前我也遇到过一个 dp+高精 的问题，没做出来很可惜，这次又找到了一个类似的问题，很高兴解决了，加油！
