Re: [閒聊] 每日LeetCode

[DJYOSHITAKA (franchouchouISBEST)]

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
推 digua: 大師