计数类Dp，对不重不漏的思考

· · 个人记录

计数类Dp，对不重不漏的思考

终于一步步学习来到计数类DP的面前了，很多时候将我困住，找不到思路的就是这一类DP。在最近系统学习DP之前，一直讲各种DP问题混在一起，不会分类分思路讨论。不同类型的Dp从不同的切入点入手。

但我一直头铁乱写，写不出来就自卑自己菜。事实上，做一道题，完成一项任务，如果要完美或者尽量好，是需要积累的。前置知识十分重要。在不会的时候做一道题，更多的是为了积累经验，让这道题成为以后自己的素材。如果在刚开始的时候就过度自信以为自己能行，失败了又开始自卑，怎么能进步呢？

这将作为我的入门题目：900. 整数划分 - AcWing题库

解法一：

​ 我们从每个新的元素对当前集合的影响考虑，每加进去一个数字使得方案总数产生变化。

可以设计这样一个状态，用 f[i] 表示和为 i 的所有方案，所存储的集合的属性是方案个数。

显而易见，总和不同的方案不可能有交集。

现在我们来考虑状态转移： f[i]=f[i] + f[i-k] ，

总和为 i-k 的方案就可以转化成总和为 i 的方案。通过这种方式来递推计算就不会产生重复。

解法二：

​ 从元素个数角度考虑，用 f[i,j] 代表有 j 个数，总和为 i 的所有方案，

​ 简单思考一下，我们发现也没有交集。<br>（反复思考集合之间的关系是为了使计算不重不漏，并且合并一些可能被包含的集合，化简计算。）

接下来，让我们来看状态转移方程，（因为思维难度较高，我实在想不出是怎么来的。）

我们考虑两种可能转移过来的状态：

一是 f[i,j] 这个集合中最小值为1的所有方案， f[i,j]=f[i,j] + f[i-1][j-1]

而是 f[i,j] 这个集合中最小值不为一的，这个就十分难想了，事实上我们可以考虑将这个集合中的每个数都减一，这样得到的集合就不含有一了，那么这个集合的数量就等价于 f[i-j,j]

状态转移方程为：f[i,j]=f[i,j] + f[i-1][j-1]

综合起来就可以得到最终的解了。