C - String Game题目链接: [http://acm.hdu.edu.cn/showproblem.php?pid=6915]
C - String Game
Clair and Bob play a game.Clair writes a string of lowercase characters, in which Bob sets the puzzle by selecting one of his favorite subsequence as the key word of the game. But Bob was so stupid that he might get some letters wrong.
Now Clair wants to know whether Bob’s string is a subsequence of Clair’s string. and how many times does Bob’s string appear as a subsequence in Clair’s string. As the answer maybe too large, you should output the answer modulo 109+7.
Input
The input may contain multiple test cases.
Each test case contains exactly two lines.
The first line is Clair’s string, and the second line is Bob’s string.
The length of both strings are no more than 5000.
Output
For each test case, output one line, including a single integer representing how many times Bob’s string appears
as a subsequence in Clair’s string.
The answer should modulo 109+7.
Sample Input
eeettt et eeettt te
Sample Output
9 0
题意
Clair和Bob玩了一个游戏。Clair写了一串小写字母，Bob通过选择一个他最喜欢的子序列作为游戏的关键字来设置谜题。
但是Bob太笨了，他可能把一些字母搞错了。
现在Clair想知道Bob的字符串是否是Clair的字符串的子序列。以及Bob的字符串作为Clair的字符串的子序列出现了多少次。【关键】
但是因为答案可能太大了，应该输出对（10的9次方+7）取模的结果。【关键】
输入样例：
输入可能包含多个测试用例。
每个测试用例包含两行。第一行是Clair的字符串，第二行是Bob的字符串。两个字符串的长度不超过5000
输出样例：
对于每个测试用例，输出一行，包括一个整数，表示Bob的字符串作为Clair的字符串的子序列出现的次数。
答案应该是对（10的9次方+7）取模。
解题思路
题目其实就是说：
给定字符串A 和字符串B 问B在A中子序列的出现次数
其实就是遍历，一个一个按顺序查找 （但计算量特别大）
先判断Bob的字符串是不是Claor的字符串的子序列，如果是则计算Bob的字符串作为Clair的字符串的子序列出现了 多少 次。
否则输出0
所以后来我们采用了动态规划的方法
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
这就是动态规划法的基本思路。
思路：
计数dp dp[i][j] 代表A串前i个中 出现B串的前j个数
每次dp[i][j]=dp[i-1][j]继承过来
当a[i]==b[j]的时候 dp[i][j]+=dp[i-1][j-1] 所有的 dp[i][0]=1
代码实现
#include<bits/stdc++.h> using namespace std; const int maxn=1e3+10; const int mod=1e9+7; int dp[maxn*5][maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); string a,b; while(cin>>a>>b) { memset(dp,0,sizeof(dp)); int n=a.size(),m=b.size(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { dp[i][j]=dp[i-1][j]; if(a[i-1]==b[j-1]) { if(j==1) dp[i][j]++; else dp[i][j]+=dp[i-1][j-1]; } dp[i][j]%=mod; } } cout<<dp[n][m]<<endl; } }
