개수 dp hdu 4055 Number String

응, 계수 dp가 뭔지 나도 몰라. 비슷한 제목은 처음이야.
제목: 'I', 'D', '를 하나만 줄까?세 가지 문자의 문자열, I는 현재 숫자가 앞의 숫자보다 크고, D는 현재 숫자가 앞의 숫자보다 작다는 것을 나타낸다?현재 비트가 작거나 클 수 있음을 나타낸다.1~n의 배열에 이 문자열을 충족시키는 몇 개가 있는지 물어보세요.
분석: 제목의 뜻을 보면 dp인 것 같은데, 역시 그렇다.dp[i][j]는 전 i개의 숫자 배열에서 숫자 j로 끝나는 배열 개수를 나타낸다.
그럼 밀고 당기는 관계는 뭘까요?
str[i-1]='I'일 때 i위의 숫자가 i-1위보다 크다는 것을 알 수 있다. dp[i][j]=dp[i-1][1]+dp[i-1][2]+...+dp[i-1][j-1]; 
str[i-1]='D'일 때 i위를 나타내는 숫자가 i-1위보다 작다는 것을 알 수 있다. dp[i][j]=dp[i-1][j+1]+dp[i-1][j+2]+...+dp[i-1][i];하지만 우리는 알아차릴 수 있다.
dp[i-1][i]는 존재하지 않으며 앞의 i-1 숫자에는 i 숫자가 나타나지 않는다.우리는 앞 i-1개의 숫자의 모든 배열에 j보다 큰 숫자를 1로 더하면 배열 방안의 수가 바뀌지 않는다는 것을 감안하여 이때 dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+...+dp[i-1][i-1];
그러나 이렇게 하면 복잡도는 O(n^3)로 시간이 초과되기 때문에 우리는 접두사와 접두사를 기록하기 위해 수조sum[i][j]를 추가하면 된다.sum[i][j]는 dp[i][1]+dp[i][2]+...+dp[i][j]

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

#define mod 1000000007
int const maxn = 1005;
char str[maxn];
long long dp[maxn][maxn];
long long sum[maxn][maxn];
//dp[i][j]      i          j       
//sum[i][j]     dp[i][1]+dp[i][2]+......+dp[i][j]

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