【计数类DP】整数划分问题

题目

解释
f[i][j]的第一维是数字n，第二维是划分的个数如果方案中的最小值是1，那么就将数字总和减去1，使得最小值为0，则f[i][j]+=f[i-1][j-1]如果方案中的最小值大于1，由一一映射的关系，每个数字都减去1，则总和减去jf[i][j]+=f[i-j][j]
代码段
#include
using namespace std;
const int mod=1e9+7,N=1100;
int f[N][N];
long long ans;
int main()
{
int n;
cin>>n;

f[0][0]=1;
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])%mod; } for(int i=1;i<=n;i++) ans=(ans+f[n][i])%mod; cout<

【计数类DP】整数划分问题最先出现在Python成神之路。