hdu 4055(dp)

제목: 길이가 n인 문자열에 I, D,?를 포함합니다.현재 문자가 다음 문자보다 작거나 크거나 작음을 나타냅니다. 이 문자열은 1~1+n이라는 숫자 서열의 배열 증감 상황을 설명하고 출력에 맞는 서열이 몇 가지가 있는지 설명합니다.문제풀이: dp[i][j]는 앞의 i자 마지막 숫자인 i+1개의 숫자가 j의 모든 가능한 서열 종류임을 나타낸다. 그러면 dp[i][j]={s[i]='I'?dp[i-1][1][1]+dp[i-1][2]+dp[i-1][2]+dp[i-1][j-1]: dp[i-1][j+1]+dp[i-1][j+1][i-1][j+2]+2]+dp[i-1]], 만약에?둘 다 계산해야 돼.마지막 결과는 dp[len][1]+...+dp[len][len+1]이다.

#include 
#include 
#define ll __int64
const int N = 1005;
const ll MOD = 1000000007;
char str[N];
ll f[N][N], sum[N];

int main() {
    while (scanf("%s", str + 1) != EOF) {
        int len = strlen(str + 1);
        memset(f, 0, sizeof(f));
        f[0][1] = 1;
        for (int i = 1; i <= len; i++) {
            sum[0] = 0;
            for (int j = 1; j <= i + 1; j++)
                sum[j] = sum[j - 1] + f[i - 1][j];
            for (int j = 1; j <= i + 1; j++) {
                if (str[i] == 'I' || str[i] == '?')
                    f[i][j] = (f[i][j] + sum[j - 1]) % MOD;
                if (str[i] == 'D' || str[i] == '?')
                    f[i][j] = (f[i][j] + sum[i] - sum[j - 1]) % MOD;
            }
        }
        ll res = 0;
        for (int i = 1; i <= len + 1; i++)
            res = (res + f[len][i]) % MOD;
        printf("%I64d
", res);
    }
    return 0;
}