Sol
f[l][r]表示l到r这段区间对应的金字塔结构种数
发现是f[l][r]是可以由比它小的区间推出来的
比如已知f[l+1][k],f[k+1][r],不难想到f[l][r]+=f[l+1][k]*f[k+1][r],if(s[l+1]==s[k]&&s[k+1]==s[r])
为什么是f[l+1][k]*f[k+1][r]呢,可以画图理解
如图,分为1,2两个部分.s[l],s[k+1],s[r]表示的是最上面的那个根结点;s[l+1],s[k]是左边子树的根结点
但是并不能直接枚举k,因为这样可能重复计数
因为当前不同的划分方式可能会得到一样的最终状态
为了避重,我们可以枚举这段区间的第一棵子树是哪一段
从而把区间分为第一棵子树与剩余的部分这两部分
可以采取区间DP的一般枚举方式(区间长度,起点,终点)
由于是树形的结构,所以也可以采用递归实现的方式(记搜)
Code
递归 Code