算法1

(完全背包模型)

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010 , mod = 1e9 + 7;

int n;
int a[N];
int 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;
}

算法2

(计数类)

$f[i][j]$表示 总和是$i$，并且由$j$个数组成的方案数
此时集合的划分是：1.该方案中最小值是1 2.该方案中最小值大于1

1. 当最小值是1时，该方案数等于舍弃该1后的方案数，因此此时的方案数是：$f[i-1][j-1]$
2. 当最小值大于1时,把每一个数都减去1后每一个数仍大于等于1，仍合法，因此此时方案数等于把当前每个数减1的方案数，即：$f[i-j][j]$;
   因此状态转移方程是：$f[i][j] = f[i - 1][j - 1] + f[i - j][j]$

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010 , mod = 1e9 + 7;

int n;
int a[N];
int f[N][N];//f[i][j]表示 总和是i，并且由j个数组成的方案数

int main()
{
    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;

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

    cout << res << endl;
    return 0;
}