题目
chokudai
地址：
at_abc211_c
解析
-
TAG:
dp动态规划 -
DESCRIPITION:
给定一个字符序列 c, h, o, k, u, d, a, i 。然后输入一个字符串，要求我们按前后顺序任意选8个字符，其组成的顺序序列等于给定的字符序列，问有多少种解法。 -
INPUT:
-
SOLUTION:
（1）这种字符串先后选字符干嘛干嘛很明显应该是动态规划，仔细一想便能想到很直观的解法。
（2）假设输入字符串为s, 给定字符序列组成的字符串 a = “chokudai” .
（3）则设
dp
[
i
]
[
j
]
dp[i][j]
d
p
[
i
]
[
j
]
表示
s[
1…
j
]
s[1…j]
s
[
1
.
.
.
j
]
内包含
a[
1….
i
]
a[1….i]
a
[
1
.
.
.
.
i
]
这个顺序的字符排列方案数。
（4）得到递推式：
if
(
s
[
i
]
=
=
a
[
j
]
)
:
d
p
[
j
]
[
i
]
=
(
d
p
[
j
]
[
i
−
1
]
+
d
p
[
j
−
1
]
[
i
−
1
]
)
if(s[i]==a[j]): dp[j][i] = (dp[j][i-1]+dp[j-1][i-1])
i
f
(
s
[
i
]
=
=
a
[
j
]
)
:
d
p
[
j
]
[
i
]
=
(
d
p
[
j
]
[
i
−
1
]
+
d
p
[
j
−
1
]
[
i
−
1
]
)
el
s
e
:
d
p
[
j
]
[
i
]
=
d
p
[
j
]
[
i
−
1
]
;
else: dp[j][i] = dp[j][i-1];
e
l
s
e
:
d
p
[
j
]
[
i
]
=
d
p
[
j
]
[
i
−
1
]
;
参考源码
#include<iostream>
#include<string>
using namespace std;
const int p = 1e9+7;
const int MAXN = 1e5;
// c, h, o, k, u, d, a, i
int dp[10][MAXN+5];
string a = "0chokudai";
int main()
{
string s;
cin>>s;
s = "0"+s; // 统一下标1开始
int l = s.length();
for(int i=0;i<=l;i++) dp[0][i]=1;
for(int i=1;i<=l;i++){
char c = s[i];
for(int j=1;j<=8;j++){
// 递推关系式实现
if(c==a[j]) dp[j][i] = (dp[j][i-1]+dp[j-1][i-1]) % p;
else dp[j][i] = dp[j][i-1];
}
}
cout<<dp[8][l]<<endl;
return 0;
}
另附一个解法：
