刀片（

计数问题一般指求一个集合 $S$ 的大小，但是一般量级都十分大，不能逐一求出 $S$ 的元素，这时候如果可以把 $S$ 分成若干不交子集，那么原答案就是这些子集的答案之和，而如果子集的计数方式刚好与原问题相同，就可以用计数dp做。

经典题型：

即求一个集合 $S_{n, k}$，其中的每个元素是一种方案，求这个集合的大小

注意到每一位都是正整数，所以 $k$ 个数的话每个数的范围是 $[1, n - k + 1]$，考虑枚举第 $k$ 位的数，那么 $S_{n, k} = \sum_{a_k=1}^{n-k+1}S_{n-a_k,k-1}$，于是令 $f_{n, k} = S_{n, k}$，dp即可。