ZOJ 3543 넘버 스트링 [2011 다롄 지역 경기][dp]

제목의 뜻
한 꿰미를 D, I,?구성된 길이가 n인 문자열은 어떤 규칙을 만족시키는 1부터 n+1까지의 배열 집합을 나타낸다. D는 이 위치의 숫자가 앞의 숫자보다 작다는 것을 의미하고 I는 이 위치의 숫자가 앞의 숫자보다 크다는 것을 의미하는가?불확정
예컨대
DI를 만족시키는 숫자 배열은 3, 1, 2, 1, 3.
1<=n<=1000, 이 조건을 충족시키는 문자열 몇 가지를 구합니다
디자인의 dp는 다음과 같다
dp[i][j]는 상기 문자열을 만족시키기 전 i-1항의 길이가 i꼬리가 j인 1부터 i까지의 배열수를 나타낸다
i-1 항목이 D인 경우
dp[i][j]=sigma(dp[i-1][k]),i-1=>k>=j
i-1 항목이 I인 경우
dp[i][j]=sigma(dp[i-1][k]),j>k>=1
마지막으로sigma(dp[n+1][k]), 1<=k<=n+1 출력
왜 이러는지, 왜냐하면 1부터 i-1까지의 배열 뒤에 j가 적혀 있을 때, 앞에 i-1의 수가 j와 같은 수보다 크면 모두 1을 더하면 새로운 1부터 i까지의 배열을 얻을 수 있기 때문이다.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
const LL MOD=1000000007;
char str[2222];
LL dp[1111][1111];
LL sum[1111][1111];
int main(){
        #ifndef ONLINE_JUDGE
                freopen("H:/in.txt","r",stdin);
        #endif // ONLINE_JUDGE
        while(scanf("%s",str+2)!=EOF){
                memset(dp,0,sizeof(dp));
                memset(sum,0,sizeof(sum));
                dp[1][1]=1;
                sum[1][1]=1;
                LL len=strlen(str+2);
                for(LL i=2;i<2+len;i++){
                        for(LL j=1;j<=i;j++){
                                if(str[i]=='D' || str[i]=='?'){
                                        dp[i][j]+=sum[i-1][i-1]-sum[i-1][j-1];
                                        dp[i][j]=(dp[i][j]+MOD)%MOD;
                                }
                                if(str[i]=='I' || str[i]=='?'){
                                        dp[i][j]+=sum[i-1][j-1];
                                        dp[i][j]=(dp[i][j]+MOD)%MOD;
                                }
                                sum[i][j]=(sum[i][j-1]+dp[i][j])%MOD;
                        }
                }
                LL ans=0;
                for(LL i=1;i<=len+1;i++) ans=(ans+dp[len+1][i])%MOD;
                printf("%lld
",ans);
        }
        return 0;
}