Squares

For any positive integer N , N = a12 + a22 +...+ an2 that is, any positive integer can be represented as sum of squares of other numbers.

Your task is to print the smallest `n ' such that N = a12 + a22 +...+ an2 .

Input 

The first line of the input will contain an integer `t ' which indicates the number of test cases to follow.

Each test case will contain a single integer `N ' (1N10000) on a line by itself.

Output 

Print an integer which represents the smallest `n ' such that

N = a12 + a22 +...+ an2 .

Explanation for sample test cases:

5 - > number of test cases

1 = 12 (1 term)

2 = 12 + 12 (2 terms)

3 = 12 + 12 + 12 (3 terms)

1 = 22 (1 term)

2 = 52 + 52 (2 terms)

Sample Input 

5
1
2
3
4
50

Sample Output 

1
2
3
1
2

---

做法 : 類同零錢問題

#include <stdio.h>
#define oo 10000
int main() {
	int t, N, i, j;
	scanf("%d", &t);
	long long DP[10001] = {};
	DP[0] = 0;
	for(i = 1; i <= 10000; i++)	DP[i] = oo;
	for(i = 1; i <= 100; i++) {
		for(j = i*i; j <= 10000; j++)
			DP[j] = DP[j] < DP[j-i*i]+1 ? DP[j] : DP[j-i*i]+1;
	}
	while(t--) {
		scanf("%d", &N);
		printf("%lld\n", DP[N]);
	}
    return 0;
}