[toc]

题目

题目描述

一个正整数 $n$ 可以表示成若干个正整数之和，形如：n = n_1 + n_2 + … + n_k，其中 n_1 \ge n_2 \ge … \ge n_k, k \ge 1。

我们将这样的一种表示称为正整数 $n$ 的一种划分。

现在给定一个正整数 $n$，请你求出 $n$ 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 $n$。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 $10^9 + 7$ 取模。

数据范围

$1 \le n \le 1000$

输入样例:

5

输出样例：

7

解法1: 完全背包法1

解法1: 完全背包法2

每个物品

状态计算：

f[i][j] � [ � ] [ � ] 表示前i个整数（1,2…,i）恰好拼成j的方案数 求方案数：把集合选0个i，1个i，2个i，…全部加起来 f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + …; f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + …; 因此 f[i][j]=f[i−1][j]+f[i][j−i]; � [ � ] [ � ]

� [ � − 1 ] [ � ] + � [ � ] [ � − � ] ; (这一步类似完全背包的推导）

作者：shwei 链接：https://www.acwing.com/solution/content/2954/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

5
1 1 1 1 1
1 1 1 2
1 2 2
2 3
1 4
5

解法2: 集合划分:按开头1

解法2: 集合划分:按开头,等价变形

解法3: 集合划分:按长度,等价变形

为了方便统计,我们把5的分解,倒过来

1 1 1 1 1
2 1 1 1
2 2 1
3 2
4 1
5

观察5的分解,末尾分成两种,

1. 等于1的
2. 大于1的

同时又观察到,还需要分解的长度来进行辅助分类

f[i,j]表示前i个元素,单调降低的情况下,和是j的可能的方案的数量,得到

$$count(5) = \sum_{i=1}^5 f[i,5]$$

因为是单调减的,如果最后的一个元素是大于1,那么所有的元素可以减1后,和f[i,j-i]对应的方案数是一样的.

如果,

f[i-1,j-1]

$$f[i,j] = f[i,j-i], \sumf[k,i-(k-1)]$$

边界

• f[1,j] = 1,只有一个位置来分,
• f[i,j] = 0,j<i,表示不够分配

总结

本题目是一个集合计数问题:

设符合题目要求的数字方案形成的集合为A = \{[n_1,n_2,\cdots,n_k],\cdots\},答案就是求|A|

这种题目我们称为计数DP类问题,它的核心就是:如何把集合划分成++不重不漏++的子集合,相当于子问题分解.

同时你应该学会等价变形的思路.