LeetCode 279. Perfect Squares — JavaScript

沒想到不是愚人節玩笑，真的是超難過 Q

Perfect Squares - LeetCode

var numSquares = function(n) {
    const dp = [0];
  
    for (let i = 1; i <= n; i++) {
        dp[i] = Number.MAX_VALUE;
        for (let j = 1; j*j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i-j*j]+1);
        } 
    }
    return dp[n];
};

i 是數字 1, 2, 3 在 dp 中最小的平方數字和， j 代表可以整除的數字平方，例如 1 被 1*1 整除，因此 dp[1] = 1， 4 被 2*2 整除， dp[4] = 1，8 扣除 2*2 = 4，dp[4] = 1，因此 1+1 = 2，代表 8–2*2–2*2=0。

最後推薦一下 shopback，連 shopee、foodpanda 都能用，我已經領了快 5000 了～

註冊ShopBack就能獲得$100獎勵金

波蘭交換學生紀錄 環遊歐洲16國