印象中好像是唯一一道自己做对的除背包以外的线性 DP 题（我太菜了 QAQ），因此想写篇题解纪念一下
题目大意
题目传送门
翻译有点问题，我这里重新翻一下
大概意思就是说，给你两个字符串s和t，求出有多少对字符串x和y，满足x是s的子串且y是t的子序列，答案对1000000007(109+7)取模
关于子串和子序列的区别，可以理解为子串是一段连续的区间，而子序列则不一定是连续的
思路
这道题乍一看其实很像最长公共子序列，唯一不同的在于对于s要取它的子串，我们类比一下最长公共子序列的状态转移方程
dp[i,j]=⎩⎪⎨⎪⎧0dp[i−1,j−1]+1max(dp[i−1,j],dp[i,j−1])(i=0 or j=0)(s[i]=t[j])(s[i]=t[j])
dp[i,j]表示的是在s的前i个字符和t的前j个字符中的最长公共子序列的长度，因此，对于这道题，我们不妨设dp[i,j]为以s的第i个字符为结尾的子串与t的前j个字符中的子序列相同的个数，同样，我们分成两种情况来讨论，一种是s[i]=t[j]，一种是s[i]=t[j]
如果s[i]=t[j]，那么当前状态首先应该包括了dp[i−1,j−1]的所有情况，因为这两个字符是相同的，那么我们相当于是可以在dp[i−1,j−1]的所有情况后面加上一个相同的字符，结果一定还是成立的，然后还应该包括dp[i,j−1]的所有情况，因为不管当前两个字符是否相同，dp[i,j−1]的所有情况肯定都适用于dp[i,j]，最后，dp[i,j]还应该包括s[i]和t[j]这对组合，因为很明显前面两种情况都没有把t[j]算进去，所以最后的状态转移方程应该是这样的
dp[i,j]=dp[i,j−1]+dp[i−1,j−1]+1
如果s[i]=t[j]，那么上面所说的dp[i−1,j−1]的情况就不适用于当前情况，也没有s[i]和t[j]这对组合，所以状态转移方程就是这样的
dp[i,j]=dp[i,j−1]
最后，由于dp[i,j]只统计了以s[i]为结尾的子串，所以最终答案应该把所有的dp[i,∣s∣]加起来，另外，不要忘记取模
参考代码
其实只要搞清楚状态转移方程了，代码什么的就很好写了，这就是你懒得写注释的理由吗！，关键是要理解思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
string a,b;
int n,m,ans,dp[5001][5001];
int main()
{
getline(cin,a);
getline(cin,b);
n=a.length();
m=b.length();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i-1]==b[j-1])
dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]+1)%mod;
else
dp[i][j]=dp[i][j-1];
for(int i=1;i<=n;i++)
ans=(ans+dp[i][m])%mod;
printf("%d",ans);
return 0;
}
|
