1 /*
2 题意; 由题可知21种货币, 给出N,问有多少种组合方式。
3 简单DP以前写过啊w(?Д?)w,又纠结好久才发现转移方程那里的 += 写成 = 。(- -||)
4 转移方程 dp[j] += dp[j-w[i]] ;
5 对于每一种货币,组合方式等于现有的加上之前有的 。
6 */
7 #include<cstdio>
8 #include<cstring>
9 #include<algorithm>
10 #define INF -999999999
11 using namespace std;
12 long long w[30],f[10005];
13 int main()
14 {
15 int n;
16 for(int i=1;i<=21;i++)
17 w[i]=i*i*i;
18 while(scanf("%d",&n)!=EOF)
19 {
20 memset(f,0,sizeof(f));
21 f[0]=1;
22 for(int i=1;i<=21;i++)
23 {
24 for(int j=w[i];j<=n;j++)
25 {
26 if(f[j-w[i]]) f[j]+=f[j-w[i]];
27 }
28 }
29 printf("%lld
",f[n]);
30 }
31 return 0;
32 }