目录
题目
DP分析
第一种方法，背包DP
代码
第二种方法（有点难想到）
代码
题目
一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 10^9+7 取模。
数据范围
1≤n≤1000
输入样例:
5输出样例：
7
DP分析
第一种方法，背包DP
我们可以将 划分为
可以理解为 由
这些物品组合成
，并且物品的数目不限。因此可以转化为完全背包问题。
状态表示：使用
- 集合：
表示从
种数字中选择，总和是
的方案。
- 属性：方案的总和
状态计算：
- 数字
选择
个，说明从前
中选，且加起来恰好是
- 数字
个，说明从前
：
- 数字
个，说明从前
：
- ...
- 数字
个，说明从前
：
那么，
优化
①
②
由①和②可得
代码
（从最后状态转移方差可以看出，方程与 无关，因此可以优化成一维）
import java.io.*;
import java.util.*;
class Main{
static int N = 1010;
static int[] f = new int[N];
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
f[0] = 1; // 初始化为1是因为，在后续 j 的更新中，本身j+0也是一种方案，每次从这+1
// DP
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
f[j] = (f[j]+f[j-i])%(1000000007);
}
}
System.out.println(f[n]);
}
}
第二种方法（有点难想到）
状态表示：使用
- 集合：
- 属性：方案的总和。
状态计算：
- 划分的所有数最小值为1 ：
- 划分中所有数全都大于1 ：
（将所有划分的数字都-1，由于全都大于1，因此-1也是大于0的，所以将i减去j个1，数字的个数仍然不变）
因此：
那么i可以划分的总和为从 的总和：
代码
import java.io.*;
import java.util.*;
class Main{
static int N = 1010;
static int[][] f = new int[N][N];
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
f[0][0] = 1; // 初始化为1是因为，在后续 i 的更新中，本身i+0也是一种方案，每次从这+1
// DP
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j] = (f[i-1][j-1]+f[i-j][j])%(1000000007);
}
}
int res = 0;
for(int i=1;i<=n;i++) res = (res+f[n][i])%(1000000007);
System.out.println(res);
}
}
