点击加号查看代码
#include<bits/stdc++.h>//前缀和优化版本,不易理解 using namespace std; #define ll long long const ll maxn=1100; const ll mod=1000000007; ll sum[maxn][maxn]; ll dp[maxn][maxn]; char str[maxn];int main() {str[0]='*';str[1]='*';scanf("%s",str+2);ll len=strlen(str)-1;sum[1][1]=1;dp[1][1]=1;for(ll i=2;i<=len;i++)for(ll j=1;j<=i;j++){if(str[i]=='I'||str[i]=='?'){dp[i][j]=(dp[i][j]+sum[i-1][j-1])%mod;}if(str[i]=='D'||str[i]=='?'){ll temp=((sum[i-1][i-1]-sum[i-1][j-1])%mod+mod)%mod;dp[i][j]=(dp[i][j]+temp)%mod;}sum[i][j]=(dp[i][j]+sum[i][j-1])%mod;}cout<<sum[len][len]<<endl; }
#include<bits/stdc++.h> using namespace std; #define ll long long const ll maxn=1100; const ll mod=1000000007; ll dp[maxn][maxn]; char str[maxn];int main() {str[0]='*';str[1]='*';scanf("%s",str+2);ll len=strlen(str)-1;dp[1][1]=1;for(ll i=2;i<=len;i++)for(ll j=1;j<=i;j++){if(str[i]=='I'){for(ll k=1;k<j;k++){dp[i][j]+=dp[i-1][k]%mod;}}else if(str[i]=='D'){for(ll k=j;k<i;k++){dp[i][j]+=dp[i-1][k]%mod;}}else{for(ll k=1;k<=i;k++){dp[i][j]+=dp[i-1][k]%mod;}}}ll ans=0;for(ll i=1;i<=len;i++){ans+=dp[len][i]%mod;}cout<<ans<<endl; // for(int i=1;i<=len;i++)//测验每一个dp是否符合预期 // for(int j=1;j<=len;j++) // { // printf("%d ",dp[i][j]); // if(j==len) // printf("\n"); // } }
思路用图表示
首先感谢糖栗子的博文http://www.cnblogs.com/tanglizi/p/9471078.html以及他的热心帮助
下面上图:
