算法1-二维朴素做法

#include <iostream>
using namespace std;
/*
完全背包问题
状态表示f[i,j]
    集合：在前i个正整数中选，和恰好为j的选法有几种的集合
    属性：count，方案数
状态计算：
    f[i-1][j-k*i]，选k个i(k从0到最大)
    其中，
        f[i,j] = f[i-1,j]+f[i-1,j-i]+f[i-1,j-2i]+...+f[i-1,j-ki]
        f[i,j-i] =        f[i-1,j-i]+f[i-1,j-2i]+...+f[i-1,j-ki]
    k使得j-ki为最小正整数
    所以f[i,j] = f[i-1,j] + f[i,j-i]

*/

const int N = 1001, mod = 1e9 + 7;
int f[N][N];
int n;

int main()
{
    cin >> n;
    // 从前i个数中选，使得和为0的方案，当然只有一种：什么都不选
    for(int i=0; i<=n; i++)
        f[i][0] = 1;
    // 从前1个数中选，即只有1，则无论什么数都只有1种选法：全选1
    for(int j=0; j<=n; j++)
        f[1][j] = 1;

    // 从上方f[1][j]的初始化可知，i的循环从2开始即可
    for(int i=2; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            // 注意判断j与i的大小关系！
            if(j >= i)
                f[i][j] = f[i-1][j] + f[i][j-i];
            else
                f[i][j] = f[i-1][j];
            if(f[i][j] >= mod)
                f[i][j] -= mod;
        }

    cout << f[n][n];

    return 0;
}

算法2-空间优化

#include <iostream>
using namespace std;

const int N = 1001, mod = 1e9 + 7;
int f[N];
int n;

int main()
{
    cin >> n;

    for(int j=0; j<=n; j++)
        f[j] = 1;

    for(int i=2; i<=n; i++)
        for(int j=i; j<=n; j++)
        {
            f[j] = f[j] + f[j-i];
            if(f[j] >= mod)
                f[j] -= mod;
        }

    cout << f[n];

    return 0;
}