思路:

状态：dp[i][j]表示以j结尾i的排列

状态转移：

如果s[i - 1]是' I '，那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + .. + dp[i-1][1]

如果s[i - 1]是‘D’，那么dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i]

用前缀和处理出sum[i][j]就不用dp[i][j]了

代码:

 

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e3+5;const int MOD=1e9+7;ll sum[N][N];ll dp[N][N];//dp[i][j]表示以j为结尾的i的排列 int main(){    ios::sync_with_stdio(false);    cin.tie(0);    string s;    sum[0][1]=1;     while(cin>>s)    {        for(int i=1;i<=s.size();i++)        {            for(int j=1;j<=i+1;j++)            {                sum[i][j]=sum[i][j-1];                if(s[i-1]!='D')sum[i][j]+=sum[i-1][j-1];                if(s[i-1]!='I')sum[i][j]+=sum[i-1][i]-sum[i-1][j-1]+MOD;                sum[i][j]%=MOD;                }        }        cout<
      
       <