题目描述
一个正整数 n 可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对 109+7 取模。
数据范围
1≤n≤1000
样例
输入样例:
5
输出样例:
7
算法1
(计数类dp) $O(n^2)$
计数类dp就是状态表示——属性是数量的dp类型
思路:将这道题看成一个完全背包问题,所谓划分,就是从1~n中选数字使之和正好为n,且每个数字可无限取(前提是和不大于n)
状态表示:
1.集合,f[i][j]表示从1~i中选,和正好等于j
2.属性:数量
状态计算:
1.集合分割:将集合分割成n分,每一份都是1~n中间的一个数,代表着这个数选几次,当我们知道一个数选几次后,就可以使用“曲线救国策略”,先减去这些数的和,看其他的部分,然而我们这里求的是一个数量,所以减之前和剪之后的情况为一种情况,故不需要加其他的东西。
综上所述,可推出:f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2i]+…+f[i-1][j-k*i];
第一次优化:
这样的暴力求解时间复杂度会是三次循环的n^3,所以我们研究一下f[i][j-1]
我们可以惊奇的发现:f[i][j-i]=f[i-1][j-i]+f[i-1][j-2i]+…+f[i-1][j-k*i];
其和f[i][j]的后半段有着惊人的相似,于是我们把他替换掉
状态转移方程就变成:f[i][j]=f[i-1][j]+f[i][j-i];
第二次优化:
然后,我们思考一下这个状态转移方程的求解顺序,我们可以得到,i-1是在i之前得出的,于是我们可以采取滚动数组优化二维数组到一维数组的方式,将转移方程变为:f[j]=f[j]+f[j-i];(注意题目要求,需要%1e9+7)
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int n;
int f[N];
int main()
{
cin>>n;
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
f[j]=(f[j]+f[j-i])%mod;//f[i][j]=f[i-1][j]+f[i][j-i];
cout<<f[n]<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla