有点被降智了，但降得不多
我先说我的\(TLE\)做法把
设\(dp_{i,j}\)表示楼梯第一行长\(i\)，最后一行长\(j\)的划分方案数
我们每次看覆盖掉左下角的矩形的右上角覆盖位置，可以得到递推式：
\[dp_{i,j} = \sum_{k=i}^{j}{dp_{i,k-1} \times dp_{1,j-k}} \]最终复杂度\(O(n^3)\)，但别忘了还有高精度的复杂度\(O(\text{玄学})\)，寄
被降智的点是什么呢？每次划分后的两个楼梯\(i=1\)，因此我们直接优化掉一维：\(dp_i\)表示楼梯长\(i\)的划分方案数，递推式同理
\[dp_{i} = \sum_{k=0}^{i - 1}{dp_i \times dp_{n-i-1}} \]我们发现这是什么？这是catalan数(catalan数无处不在)
然后我们直接用公式\(O(1)\)求即可
标签：P2532,复杂度,AHOI2012,catalan,楼梯,树屋,sum,dp From： https://www.cnblogs.com/fox-konata/p/17702053.html