算法1

(完全背包) $O(n^2)$

可以设f[][]为在前i个中选且总数为j的方案数。
不选为f[i][j]=f[i-1][j];即不选第i个，则在前i-1个中选，总数为j的方案数
选为f[i-1][j-i]即选第i个，则总数为j-i的方案数.

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=4e3+10;

typedef long long ll;

int n;
ll f[N];//在前i个数中选且总和为j的的数的个数
int mod=2147483648;

int main()
{
    scanf("%d",&n);
   // cin>>n;

  /*  f[0][0]=1;//这个只能过8个点
    for(int i=1;i<n;i++)
    for(int j=0;j<=n;j++)
    {
     f[i][j]=f[i-1][j]%mod;//不选第i个
    for(int k=1;k*i<=j;k++)
    if(j>=k*i) f[i][j]=(f[i][j]+f[i-1][j-k*i])%mod;//选第i个
    }

    cout<<f[n-1][n];
    */
  /*  f[0]=1;
    for(int i=1;i<n;i++)
    for(int j=n;j>=i;j--)
    {
        for(int k=1;k*i<=j;k++)//这里k*i都在1~j中,所以这里其实可以省一维，也可以过但时间是O(n^2)的10倍
        if(j>=k*i) f[j]=(f[j]+f[j-k*i])%mod;
    }

    printf("%d",f[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;
    }

    printf("%d",f[n]);


    return 0;
}