莫欺少年穷，修仙之旅在这开始—>算法基础课题解

完全背包问题求方案数

推导过程：

$因为\ \ 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]$

$所以\ \ f[i][j]=f[i-1][j]+f[i][j-i]$

完整代码

#include<bits/stdc++.h>

using namespace std;

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

int n;
int f[N]; //只从前 i 个物品中选，体积恰好是 j 的方案数

int main()
{
    cin>>n;

    f[0]=1; //什么都不选也是一种方案
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++) //保证了 f[j-i] 是 f[i][j-i]
            f[j]=(f[j]+f[j-i])%mod;

    cout<<f[n]<<endl;

    return 0;
}