AcWing 900. 整数划分
原题链接
简单
作者:
B1ackGod
,
2021-02-09 15:50:11
,
所有人可见
,
阅读 375
核心:动态规划:类比完全背包的做法,数字的选择不限次数、顺序
- 状态定义:f[i][j]表示从前i个数(1~i)中选若干个数,总和恰好为j的所有选法。
注意:这里i可以取0,就可以表示为前0个数,没有数字。
- 属性:数量
- 状态计算:用数字i的使用数量来划分集合
①—f[i][j]=f[i-1][j]+f[i-1][j-1i]+f[i-1][j-2i]…
②—f[i][j-i]= f[i-1][j-1i]+f[i-1][j-2i]…
因此,①等价于f[i][j]=f[i-1][j]+f[i][j-i];
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N][N];
int n;
int main(){
cin>>n;
for(int i=0; i<n; i++)
f[i][0]=1; //前i个数都不选,也是一种方案
for(int i=1; i<=n; i++)
for(int j=0;j<=n;j++)
{
f[i][j]=f[i-1][j]%mod;
if(j>=i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
}
printf("%d",f[n][n]);
return 0;
}