AcWing 900. 基础课二刷之第59题加强巩固 整数划分*
原题链接
简单
作者:
Snow_raw
,
2021-08-26 20:00:50
,
所有人可见
,
阅读 176
题目描述
一个正整数 n 可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中 n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对 109+7 取模。
数据范围
1≤n≤1000
样例
5
输出
7
算法
dp完全背包
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const int mod=1e9+7;
int f[N];
int main(){
int n;
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;
}
cout<<f[n]<<endl;
return 0;
}
将问题转化为dp完全背包,先朴素再优化