Re: [閒聊] 每日LeetCode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1年前 (2024/02/08 16:45)推噓1(1推 0噓 0→)留言1則, 1人參與討論串660/719 (看更多)
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);
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707381916.A.0A4.html
推
02/08 16:47,
1年前
, 1F
02/08 16:47, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 660 之 719 篇)：