题目描述
一个正整数$n$可以表示成若干个正整数之和,形如:$n=n_1+n_2+…+n_k$,其中 $n_≥n_2≥…≥n_k,k≥1$。
我们将这样的一种表示称为正整数$n$的一种划分。
现在给定一个正整数$n$,请你求出$n$共有多少种不同的划分方法。
输入格式
共一行,包含一个整数$n$。
输出格式
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对$10^9+7$取模。
数据范围
$1≤n≤1000$
样例
5
输出
7
算法1
朴素DP
- 每个方案和中的正整数单调递减
- $n_1≥n_2≥…≥n_k,k≥1$ — 不考虑顺序
- 将正整数$n$看作背包容量,物品有无限个,体积为$1\sim n$,求恰好装满背包的方案数
- 任何一种表示方法$n=n_1+n_2+…+n_k$都可以看作背包问题选法,选择了物品$n_1,n_2,…,n_k$
- 因为不考虑顺序,每个划分方式对应背包的一种选法
时间复杂度
$O(n^3)$
C++ 代码
// 朴素
#include <iostream>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int n;
int f[N][N];
int main()
{
scanf("%d", &n);
// 初始化从1~i中选总体积不超过j的选法数量
for (int i = 0; i <= n; i ++) f[i][0] = 1;
for (int i = 1; i <= n; i ++) // 枚举1~n
for (int j = 1; j <= n; j ++) // 枚举容量,因为j=0已经初始化了,从1开始枚举
for (int k = 0; k * i <= j; k ++) // 枚举选几个
f[i][j] = (f[i - 1][j - k * i] + f[i][j]) % MOD;
printf("%d\n", f[n][n]);
return 0;
}
算法2
二维优化
- $f[i,j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2\times i]+…+f[i-1][j-s\times i]$
- $f[i,j-1]=f[i-1][j-i]+f[i-1][j-2i]+…+f[i-1][j-si]$
- 合并同类项:$f[i,j]=f[i - 1][j]+f[i][j-i]$
时间复杂度
$O(n^2logn)$
C++ 代码
// 二维优化
#include <iostream>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int n;
int f[N][N];
int main()
{
scanf("%d", &n);
// 初始化f[0][0]
// 后续计算f[i][0]都会因为体积不够导致只能从f[i-1][0]这种状态转移过来-f[i][0]=f[i-1][0]
f[0][0] = 1;
for (int i = 1; i <= n; i ++) // 枚举1~n
for (int j = 0; j <= n; j ++) // 枚举容量
{
f[i][j] = f[i - 1][j];
if (j >= i) f[i][j] = (f[i][j] + f[i][j - i]) % MOD;
}
printf("%d\n", f[n][n]);
return 0;
}
算法3
一维优化
- 对二维优化进行降维打击
时间复杂度
$O(n^2logn)$
C++ 代码
// 一维优化
#include <iostream>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int n;
int f[N];
int main()
{
scanf("%d", &n);
f[0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++) // 直接从i开始从小到大枚举
f[j] = (f[j] + f[j - i]) % MOD;
printf("%d\n", f[n]);
return 0;
}