acwing900. 整数划分

分析

1. 可以将整数n看成体积大小为n的背包，用来装体积为1-n的东西，可以转化为完全背包问题。
2. f[i][j]表示在1-i中选，总数为j的选法。
3. 状态转移方程：f[i][j]=(f[i-1][j]+f[i][j])%mod

#include<iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int n,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;
    cout<<f[n]<<endl;
    return 0;
}