Topcoder SRM 590 DIV2 HARD

took me so much time on understanding this DP approach...
Solution

/* Topcoder SRM */
/*****************************************************************************/
const int mod=1e9+7;
long long solve(string c) {
    vector<int> x;
    for (int i=0; i<sz(c); i++) {
        if (c[i]!='.') {
            x.pb(i); 
        }
    }
    int t=sz(x), n=sz(c);
    int d[t+1][n+1];
    for (int i=t; i>=0; i--) {
        for (int p=n; p>=0; p--) {
            long &r=d[i][p];
            if (i==t) {
                r=1;
            } else {
                int hi=n-(t-i), lo=p;
                c[x[i]]=='D'?lo=max(p, x[i]):hi=min(hi, x[i]);
                r=0;
                for (int j=lo; j<=hi; j++) {
                    r+=d[i+1][j+1]; 
                }
                r%=mod;
            }
        }
    }
    return d[0][0];
}
int FoxAndShogi::differentOutcomes(vector <string> board) {
    int n=sz(board);
    long long r=1;
    for (int i=0; i<n; i++) {
        string c="";
        for (int j=0; j<n; j++) {
            c+=board[j][i];
        }
        r*=solve(c);
        r%=mod;
    }
    return r;
}
/*****************************************************************************/