Zoj 3543 Number String (dp) - 2011 ACM-ICPC Dalian Regional Contest Problem E

또 하나의 dp.시합할 때 수학 문제인 줄 알고 규칙적인 공식을 계속 찾고 있었다.
/**
제목: {1,2,3}으로 구성된 배열 132는 문자열'아이디','I'는 인크리에이트,'D'는 Decrease,'132'에 대한 배열은 1<3>2이기 때문에 대응하는 문자열은'아이디'다.이제 반대로 'I', 'D', '? 만 포함하는 문자열을 입력하십시오.세 가지 문자, 문자열 길이 n(n<=1000), 출력 {1.n+1}으로 구성된 배열에서 이 문자열의 개수와 1000000007을 충족시킵니다.문제풀이: dp[i][j]는 길이가 i로 j로 끝나는 합법적인 배열 개수(1...i로 구성된 배열)를 나타낸다.또 하나의 결론을 명확히 해야 한다. i-1 길이의 문자열을 정하면 {1,2,......,i}로 구성된 합법적인 배열수와 {1,2,.....,j-1,j+1,......,i+1}로 구성된 합법적인 배열수는 같다.if ( s[i] == 'I' ) dp[i][j] = dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j-1]; if ( s[i] == 'D' ) dp[i][j] = dp[i-1][j] + dp[i-1][j+1] +...+ dp[i-1][i-1]; if ( s[i] == '?' ) dp[i][j] = dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][i-1]; 시간 복잡도는 O(n^3)이지만sum[i][j]를 부분적인 구화로 정의하면 O(n^2)로 바뀐다.
**/

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;
const int MAXN = 1000 + 5;
const LL  MOD  = 1000000007;

char s[MAXN];
LL   dp[MAXN][MAXN], sum[MAXN][MAXN];

int main()
{
    while ( scanf("%s", s+2) != EOF )
    {
        int len = strlen(s+2) + 1;
        sum[1][1] = dp[1][1] = 1;
        for (int i = 2; i <= len; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                if ( s[i] == 'I' )
                    dp[i][j] = sum[i-1][j-1];
                else if ( s[i] == 'D' )
                    dp[i][j] = sum[i-1][i-1] - sum[i-1][j-1];
                else
                    dp[i][j] = sum[i-1][i-1];
                sum[i][j] = (sum[i][j-1] + dp[i][j]) % MOD;
            }
        }
        printf("%lld
", (sum[len][len] + MOD) % MOD); //   sum            ，           
    }
    return 0;
}