Description

给定一个数字 \(n\)，表示有一个长度为 \(n\) 的序列，又给定一个长度为 \(n-1\) 字符串 \(s\)，里面仅包含 \(<\) 和 \(>\)。

当 \(1 ≤ i ≤ n - 1\) 时，s[i] 表示数列中第 \(i\) 个元素与第 \(i + 1\) 个元素的关系。

求满足字符串 \(s\) 关系的 \(1\) ~ \(n\) 的排列一共有多少种，方案数对 \(10^9+7\) 取模。

constraints

\(2 ≤ n ≤ 3000\)

Solution 1 TLE

考虑DP。

设 f[i][j] 表示已经考虑了前 \(i\) 个位置，且第 \(i\) 位上，填的数字是第 \(j\) 小的总方案数。

不难想到初始状态即用 \(1\) 填了 \(1\) 位，即 f[1][1] = 1 。

由于每一位必由前一个位置转移过来，所以可以分两种情况：

• 这个位置是 <，根据状态定义，前一位要比这个小，即 f[i][j] += f[i - 1][k] (k < j)；

• 这个位置是 >，前一位要比这个大，但是，在 \(i-1\) 时的第 \(j\) 小，由于现在加入了一个第 \(j\) 小的数，将上次的第 \(j\) 小变成了现在的 \(j+1\) 小，所以需要加上 f[i - 1][k]。即 f[i][j] += f[i - 1][k] (j ≤ k < i)；

由于这个复杂度是 \(O(n^3)\)，因此还是会超时。

Solution 2 AC

上面的算法复杂度较高，考虑优化，但状态已经优化到了二维，考虑优化转移。

发现最内层循环时，由于要统计上一个数的所有可能转移的位置，耗费了较多时间。

由于可能转移的位置肯定都是一个连续的段，且是它们之和，可以前缀和优化。设 sum[j] 表示从 f[i-1][1]到f[i-1][j]` 的数值之和，转移时直接计算即可。

时间复杂度为 \(O(n^2)\)。

核心代码：

	f[1][1] = 1;//初始值
	for(int i = 2; i <= n; i++)
	{
		memset(sum, 0, sizeof sum);//每一次sum要清空
		for(int j = 1; j <= i - 1; j++)
		{
			sum[j] = sum[j - 1] + f[i - 1][j];//sum记录前缀和
		}
		for(int j = 1; j <= i; j++)
		{
			if(s[i] == '<')//处理小于号
			{
				f[i][j] = (f[i][j] + sum[j - 1] - sum[0]) % MOD;
			}
			else//处理大于号
			{
				f[i][j] = (f[i][j] + sum[i - 1] - sum[j - 1]) % MOD;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)//最后答案是f[n][i]的总和
	{
		ans = (ans + f[n][i]) % MOD;
	}

Code

Solution 1 代码
Solution 2 有注释代码