组合型

需要排列组合的计数型DP

树上也可以

组合计数

c[k][n]=n!\(k!(n-k)!)

c[k][n]=c[k][n-1]+c[k-1][n-1]

边界：c[0][n]=c[n][n]=1

卡特兰数

卡特兰数：

状态：f[i]表示i个元素时的卡特兰数

转移：f[n]=sum{f[i]f[n-1-i]},i in [0,n-1]

边界：f[0]=1

可以求出递推公式

$C_{n+1}=\frac{2(2n+1)}{n+2}C_n$

$C_{n}=\frac{2(2n-1)}{n+1}C_{n-1}$

On递推

应用场景

1. 括号序列问题

   n对括号正确匹配数目

   有n对()括号，试问可以组成多少种合法正确的括号序列？

2. 出栈顺序问题

3. 括号化：

   一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列

   类似买票找零

4. 二叉树计数问题

   给定节点组成二叉搜索树

   给定 n 个节点，能构成多少种形状不同的二叉树。

5. 凸多边形三角划分

   将一个凸多边形区域分成三角形区域的方案数。

   在圆上选择 2n 个点，将这些点对连接起来使得所得到的 n 条线段不想交的方案数。

---

K 个逆序对数组 lc629.

状态：f[i][j]表示前i个数字，恰好构成j个逆序对

转移：f[i][j]=f[i][j-1]-f[i-1][j-i]+f[i-1][j]

边界：f[n][k]