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);
}