Number String(HDU 4055,动态规划递推,前缀和优化)

点击加号查看代码

#include<bits/stdc++.h>//前缀和优化版本,不易理解

using namespace std;

#define ll long long

const ll maxn=;

const ll mod=;

ll sum[maxn][maxn];

ll dp[maxn][maxn];

char str[maxn];

int main()

{

    str[]='*';

    str[]='*';

    scanf("%s",str+);

    ll len=strlen(str)-;

    sum[][]=;

    dp[][]=;

    for(ll i=;i<=len;i++)

        for(ll j=;j<=i;j++)

        {

            if(str[i]=='I'||str[i]=='?')

            {

                dp[i][j]=(dp[i][j]+sum[i-][j-])%mod;

            }

            if(str[i]=='D'||str[i]=='?')

            {

                ll temp=((sum[i-][i-]-sum[i-][j-])%mod+mod)%mod;

                dp[i][j]=(dp[i][j]+temp)%mod;

            }

            sum[i][j]=(dp[i][j]+sum[i][j-])%mod;

        }

        cout<<sum[len][len]<<endl;

}

前缀和优化版本,不易理解

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxn=;

const ll mod=;

ll dp[maxn][maxn];

char str[maxn];

int main()

{

    str[]='*';

    str[]='*';

    scanf("%s",str+);

    ll len=strlen(str)-;

    dp[][]=;

    for(ll i=;i<=len;i++)

        for(ll j=;j<=i;j++)

        {

            if(str[i]=='I')

            {

                for(ll k=;k<j;k++)

                {

                    dp[i][j]+=dp[i-][k]%mod;

                }

            }

            else if(str[i]=='D')

            {

                for(ll k=j;k<i;k++)

                {

                    dp[i][j]+=dp[i-][k]%mod;

                }

            }

            else

            {

                for(ll k=;k<=i;k++)

                {

                    dp[i][j]+=dp[i-][k]%mod;

                }

            }

        }

        ll ans=;

        for(ll i=;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以及他的热心帮助

下面上图: