P2246 SAC#1 - Hello World（升级版）题解
P2246 SAC#1 - Hello World（升级版）题解
大致意思：
就是在一串字母中找出 HelloWorld 子序列出现的次数。
大致思路：
-
暴力，跟据每个字母的位置及相同字母的位置，进行枚举和判断，时间
O (n) 。 -
动态规划，因为题目提供的模板串长度比较小，所以我们可以将它存入数组，一位一位枚举。而我们知道因为是子序列，前面的情况也要包含进去，所以第
i 项需要加上i - 1 项，因此得出公式dp_{i} = dp_{i} + dp_{i - 1} ，时间复杂度依然为O (n) 。
这道题我选择了第二种方法来做。
代码实现：
#include<bits/stdc++.h>
using namespace std;
int dp[20];
char s,c[20]={"helloworld"};
const long long mod=1000000007;
int main(){
dp[0]=1;
while(1){
s=getchar();
if(s==EOF){
cout<<dp[10]<<endl;
return 0;
}
char k=s+32;
for(int i=9;i>=0;i--){
if(k==c[i]||s==c[i]){
dp[i+1]=(dp[i]+dp[i+1])%mod;
}
}
}
return 0;
}这样这道题就完成啦！！！