HDU4055
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4055
思路：dp[i][j]表示处理前i个字符以j结尾可能的序列数。
当a[i]=='I'时，dp[i][j]=sum(dp[i-1][k]),（1<=k<=j-1）， 可进一步化为dp[i][j-1]+dp[i-1][j-1]。
当a[i]=='D'时，dp[i][j]=sum(dp[i-1][k]),(j<=k<=i-1)，可进一步化为dp[i][j+1]+dp[i-1][j]。
当a[i]=='?'时，dp[i][j]=sum(dp[i-1][k]),(1<=k<=i-1)。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3 + 5;
const int mod = 1e9 + 7;
char a[N];
int dp[N][N];
int main()
{
while(~scanf("%s",a+2))
{
memset(dp,0,sizeof(dp));
int len = strlen(a+2) + 1;
dp[1][1] = 1;
for(int i = 2 ;i <= len ;i++)
{
if(a[i] == 'I')
{
for(int j = 2 ;j <= i ;j++)
dp[i][j] = (dp[i][j-1] + dp[i-1][j-1]) % mod;
}
else if(a[i] == 'D')
{
for(int j = i-1 ;j >= 1 ;j--)
dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % mod;
}
else
{
int sum = 0;
for(int j = 1 ;j <= i-1 ;j++)
sum = (sum + dp[i-1][j]) % mod;
for(int j = 1 ;j <= i ;j++)
dp[i][j] = sum;
}
}
int ans = 0;
for(int i = 1 ;i <= len ;i++)
ans = (ans + dp[len][i]) % mod;
printf("%d
",ans);
}
return 0;
}