题目分析

不是很难的区间dp,用l[i][j]表示i到j这端最后插入的是a[i]的方案数,r[i][j]则表示i到j这端最后插入的是a[j]的方案数,就很容易推出状态转移方程:

然后初始化是l[i][i]=1(或者r[i][i]=1;但是不可以两个都等于1,不然会重复计算)

代码