279. Perfect Squares
n必定能由一组可重复的正整数的平方和所组成
找出最少个数的数组能透过平方和组出n
回传个数
想了一下无脑DFS+memorization
1<=n<=10000 直接无脑开vector 对不起
for loop 从大到小或小到大 想了想好像没差(吧)
跑起来也确实差不多
int helper(vector<int>& cache, int n) {
if(cache[n] != -1) {
return cache[n];
}
int ans = INT_MAX;
for(int i=1; (i*i)<=n; i++) {
ans = min(ans, helper(cache, n-(i*i))+1);
}
cache[n] = ans;
return ans;
}
int numSquares(int n) {
vector<int> cache(10001,-1);
cache[0] = 0;
return helper(cache, n);
}