Ingenuous Cubrency UVA - 11137 立方数之和 递推

输入正整数n (n ζ10000) ，求将n 写成若干个正整数的立方之和有多少种方法。
比如21 有3 种写法: 21=13+13+13+...+13=23+13+13+13+...+13=23+23+13+13+ 13+ 13+ 1 3 。
77 有22 种写法， 9999 有440022018293 种写法。
分析:建立多段图。结点d(i,j)表示"使用不超过i 的整数的立方，累加和为j" 这个状态，设d(iJ)为从(0，0)到(iJ)的路径条数，则最终答案为d(21,n) (因为对于题目范围， 22^3>n) 。这个多段图的特点是每个结点一步只能走到下一个阶段的结点，因此我们可以一个阶
段一个阶段的计算，代码如下。

实际上每次都是从左向右递增覆盖的，二维数组可以降为一维。

#include <cstdio>
const int N = 10000, I = 21;//22^3 = 10648
long long d[N+5];
int main(int argc, char** argv) {
	int n;
	d[0] = 1;
	for(int i = 1; i <= I; i++)
		for(int j = 0; j+i*i*i <= N; j++)
				d[j+i*i*i] += d[j];
	while( ~scanf("%d",&n))	
		printf("%lld\n",d[n]);
	return 0;
}