学步园

不错的dp

long long 果然比int慢好多

#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define N 1010
#define mod 1000000007
using namespace std;
typedef long long ll;
int sum[N][N];
char s[1010];
int main(){
    int i,j,n;
    while(scanf("%s",&s)==1){
        n=strlen(s)+1;
        memset(sum,0,sizeof(sum));
        sum[1][1]=1;
        for(i=2;i<=n;i++){
            for(j=1;j<=i;j++){
                if(s[i-2]=='I' || s[i-2]=='?')
                    sum[i][j]=sum[i-1][j-1];
                if(s[i-2]=='D' || s[i-2]=='?')
                    sum[i][j]=((sum[i][j]+sum[i-1][i-1]-sum[i-1][j-1])%mod+mod)%mod;
                sum[i][j]=(sum[i][j]+sum[i][j-1])%mod;
            }
        }
        printf("%d\n",sum[n][n]);
    }
}

可参考（http://blog.csdn.net/shiqi_614/article/details/7983298）