【SOJ-1865整数分割】最適化

#define N 501
ll d[N][N];
ll q(ll n, ll m)
{
    if ((n < 1) || (m < 1)) return 0;
    if (n == 1 || m == 1) return 1;
    if (n < m) return q(n, n);
    if (n == m) return q(n, m - 1) + 1;
    return q(n, m - 1) + q(n - m, m);
}
int main()
{
	memset(d, 0, sizeof(d));
	ll i, j, k;
	for (i = 1; i <= N; ++i) d[i][1] = d[1][i] = 1;
	for (i = 0; i < N; ++i) {
		for (j = 0; j < N; ++j) {
			if (i < 1 || j < 1) d[i][j] = 0;
			else if (i == 1 || j == 1) d[i][j] = 1;
			else if (i < j) d[i][j] = d[i][i];
			else if (i == j) d[i][j] = d[i][j - 1] + 1;
			else {
				d[i][j] = d[i][j - 1];
				if (i - j > 0) d[i][j] += d[i - j][j];
			}
		}
	}
	ll n;
	while (scanf("%lld", &n) == 1 && n) {
		printf("%lld
", d[n][n]);
	}
	return 0;
}