dp

· · 个人记录

刀片（

计数dp

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

经典题型：

给定一个正整数 n，求有多少个把 n 划分成 k 个正整数的和的方案，位置调换视为不同的划分方案。

即求一个集合 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即可。

概率dp

动态dp

dp套dp

dp优化

决策单调性

slop trick

wqs二分