一道算法题目，求高人指点！多谢

一道算法题目，求高人指点！谢谢！
Description

给定一个N表示字符串的长度，问此长度的由左右小括号和小写字母a构成的合法的字符串有多少个

合法的字符串如下定义：

1 空串是合法的

2 如果P是合法的，那么aP也是合法的

3 如果P是合法的，那么(P)也是合法的

4 如果P和Q都是合法的，那么PQ也是合法的

请输出答案除以19301的余数

Input Format

N(0<N≤3333)

Output Format

答案除以19301的余数

Sample Input 1
1
Sample Output 1
1
Sample Input 2
3
Sample Output 2
4
Sample Input 3
4
Sample Output 3
9

就是这样一道题，请问大家思路是什么呢？能有代码参考更好了。
谢谢！
[解决办法]
其实也不是特别复杂，是我自己想错了，直接迭代就可以了，而且也不是很慢。。。

int main(void)
{
unsigned int res[3334]={0};

res[0]=1;
res[1]=1;
res[2]=2;
res[3]=4;
for (int i =4 ;i < 3334;i++)
{
res[i]=res[i-1];
for (int j =0;j<i-1;j++)
{
res[i]+=res[i-2-j]*res[j];
res[i]=res[i]%19301;
}
}

return 0;
}

查看更多 下一篇