範例程式碼 uva1650
//uva1650
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 1024
#define MOD 1000000007
using namespace std;
char s[MAXN];
int dp[MAXN][MAXN], sum[MAXN][MAXN];
int main() {
while (scanf("%s", s) == 1) {
int n = (int) strlen(s);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
dp[0][1] = sum[0][1] = 1;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= i + 2; j++) {
if (s[i] == 'I' || s[i] == '?')
dp[i+1][j] = (dp[i+1][j] + sum[i][j-1]) % MOD;
if (s[i] == 'D' || s[i] == '?')
dp[i+1][j] = (dp[i+1][j] + (sum[i][i+1] - sum[i][j-1]) % MOD + MOD) % MOD;
sum[i+1][j] = (sum[i+1][j-1] + dp[i+1][j]) % MOD;
}
}
printf("%d\n",sum[n][n+1]);
}
return 0;
}