二维dp

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
const int P=1e9+7;

int n;
int f[N][N];

int main(){
    // 完全背包问题
    memset(f, 0x00, sizeof f);
    cin>>n;
    f[0][0]=1; // f[i][j]表示使用前i个正整数组成j的方案数量
    for(int i=1; i<=n; ++i)
        for(int j=0; j<=n; ++j){
            f[i][j]=f[i-1][j];   
            if(j>=i) f[i][j]=(f[i][j], f[i-1][j]+f[i][j-i])%P;
        }
    cout<<f[n][n]<<endl;


    return 0;
}

一维数组优化

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
const int P=1e9+7;

int n;
int f[N];

int main(){
    // 完全背包问题
    memset(f, 0x00, sizeof f);
    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])%P;
        }
    cout<<f[n]<<endl;

    return 0;
}

求和的集合划分

#include <bits/stdc++.h>
using namespace std;

const int N=1005;
const int P=1e9+7;

int n;
int f[N][N];

int main(){
    // 从和的角度得到状态转移方程
    memset(f, 0x00, sizeof f);
    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])%P;

    int res=0;
    for(int i=1; i<=n; ++i) res=(res+f[n][i])%P;
    cout<<res<<endl;

    return 0;
}