E 礼物(1)题解:
dp做法:设\(dp_{ij}\)是使用i元分成有序的j份的方案数。则有转移方程
\(dp_{ij}=dp_{k j-1} \ for \ k<i\)

组合数学做法:

经典例题，可以知道答案是\(C_{i-1}^{j-1}\)。

dp Code:

#include<bits/stdc++.h>
using namespace std;
int n,mod=1e9+7,dp[2005][20];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)dp[i][1]=1;
    for(int i=1;i<=19;i++)dp[i][i]=1;
    for(int i=2;i<=19;i++)for(int j=i+1;j<=n;j++)for(int k=i-1;k<j;k++)
        dp[j][i]=(dp[j][i]+dp[k][i-1])%mod;
    cout<<dp[n][19]<<endl;
    return 0;
}