请耐心看完题解，挑选合适的方法做题

题意

给定 n 和一个长度为 n−1 的字符串（由 '<' 和 '>' 组成），求数列 1,2,...,n 有多少种排列，使得相邻数之间的大小关系与字符串中大于号小于号相符合，答案对 1e9+7 取模。

SOLUTION 1

思路

既然是dp，那就开一个数组f[i][j]代表在前i个位置中填1~i,最后一位填j的情况数。所以就是枚举第i位之前填数的方案。 可以得到转移方程:

1.s[i-1]='<'时，f[i][j]=f[i-1][1]~f[i-1][j-1]的和。

2.s[i-1]='>'时，f[i][j]=f[i-1][j]~f[i-1][i-1]的和。

但这样的转移是O(n)的，再加上枚举，时间复杂度就成了O(n^3),所以我们需要优化掉一层，可以用前缀和来解决。 于是再开一个sum[N][N]来前缀和f[i][j]的状态转移，最后的答案就会是sum[n][n]。

细节

依旧讲细节： 初始化问题，f[1][1]，sum[1][1]~sum[i][n]都是1，因为只有一个数，无论怎样都符合条件。

最后上标准代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll P=1e9+7;
ll n,f[3010][3010],sum[3010][3010];
char s[3010];
int main()
{
    scanf("%lld",&n);
    scanf("%s",s+1);
    f[1][1]=1;
    for(ll i=1;i<=n;i++)sum[1][i]=1;
    for(ll i=2;i<=n;i++)
	{
		if(s[i-1]=='<')for(ll j=1;j<=i;j++)
		{
			f[i][j]=sum[i-1][j-1]%P;
			//根据f的定义只能填i，直接从前一种情况继承过来
		    sum[i][j]=(sum[i][j-1]+f[i][j])%P;
		}
        if(s[i-1]=='>')for(ll j=1;j<=i;j++)
		{
            f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+P)%P;
            //同理，从比i小的数中选，所以j~i-1的前缀和
			sum[i][j]=(sum[i][j-1]+f[i][j])%P;
        }
    }
    printf("%lld\n",sum[n][n]%P);
    return 0;
}

如果想要简洁一点的代码，我们可以发现原来代码中j的枚举和前缀和的处理是相同的，所以可以简化成这样：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll P=1e9+7;
ll n,f[3010][3010],sum[3010][3010];
char s[3010];
int main()
{
    scanf("%lld",&n);
    scanf("%s",s+1);
    f[1][1]=1;
    for(ll i=1;i<=n;i++)sum[1][i]=1;
    for(ll i=2;i<=n;i++)
	{
        for(ll j=1;j<=i;j++)
		{
            if(s[i-1]=='<')f[i][j]=sum[i-1][j-1]%P;
            if(s[i-1]=='>')f[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+P)%P;
            sum[i][j]=(sum[i][j-1]+f[i][j])%P; 
        }
    }
    printf("%lld\n",sum[n][n]%P);
    return 0;
}

SOLUTION 2

我们也可以让f[i][j]表示另一种东西：填到第i个位置时，前面一个数是当前数列中第j大的。 所以状态转移也分两种：

1.s[i-1]='<'时，f[i][j]=f[i-1][1]~f[i-1][j-1]的和。

2.s[i-1]='>'时，f[i][j]=f[i-1][j]~f[i-1][i-1]的和。

虽然和上一种方法的状态转移一样 但优化的思路就不一样了：

1.s[i-1]='<'时，第i个位置所选的数要比前一个大，前一个在数列中的排名为j，所以要使得选的数在数列中的排名为j-1，于是f[i][j]=f[i][j-1]+f[i-1][j-1]。

2.s[i-1]='>'时，同上，要使得选的数的排名为j+1，于是f[i][j]=f[i][j+1]+f[i-1][j]。

因为此时f数组的状态转移为递推，已包含前缀和，所以空间会比solution1少一点。

细节

这个思路的细节就会有点多：

1.初始化同上。

2.两种转移方程的递推方向不同，s[i]为'<'时，要填的数会更大，所以从前往后；s[i]为'>'时，要填的数会更小，所以从后向前。

3.两中情况都舍去最开始的那个j，因为最开始的数转移了就是没转移，最前面的前面没有状态数，最后面的后面还没转移到。

4.因为f[i][j]意义的不同，答案的处理也会不同，第一个数可以在数列中成为任意大小，所以需要累加f[n][1]到f[n][n]。

最后来到AC代码环节：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll P=1e9+7;
ll n,f[3010][3010];
char s[3010];
int main()
{
	scanf("%lld",&n);
	scanf("%s",s+1);
	f[1][1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(s[i-1]=='<')for(ll j=2;j<=i;j++)f[i][j]=(f[i-1][j-1]+f[i][j-1])%P;
		else for(ll j=i-1;j>=1;j--)f[i][j]=(f[i-1][j]+f[i][j+1])%P;
	}
	ll ans=0;
	for(ll i=1;i<=n;i++)ans=(ans+f[n][i])%P;//累加 
	printf("%lld\n",ans);
	return 0;
}