题目描述

blablabla

思路

因为至少为2个,所以我们设置枚举边界为n-1,然后很容易写出方程f[j]+=f[j-i],假如这个数能够由上个数转移过来,那么上个的方案数,这个数都能使用,然后这个题目就解决了.

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

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2147483648;
const int N=4005;
ll f[N];
int main()
{
    int n;
    scanf("%d",&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;
}