Leetcode 279. Perfect Squares

Perfect Squares

Perfect Squares :

給定一個正整數n,找出最少要用幾個完全平方數(1, 4, 9, 16…)才能夠找出總和等於n的方法。例如給定n=12,則返回3,因爲12=4+4+4;給定n=13,則返回2,因爲13=4+9.

Python

當 n=13,dp[13]的答案可能是dp[12] + 1,也有可能是dp[9] + 1,也有可能是dp[4] + 1,要從上面的答案找出最小值,使用動態規劃。初始化dp[0] = 0,dp[1] = 1,dp[i] = n,遍歷2到n,不斷更新dp[i]。

以n = 13為例子, 13 – 2*2 = 9, 那麼dp[13] = min(dp[13],dp[9] + 1), 我們要求dp[9]的最小完美平衡的個數,加上1就是dp[13]的結果。

class Solution:
    def numSquares(self, n: 'int') -> 'int':
        #初始化
        dp = [n]*(n+1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n+1):
            j = 1
            while j*j <= i:  
                dp[i] = min(dp[i], dp[i-j*j] + 1)   
                j += 1
        return dp[-1]

C++

動態規劃

定義一個數組dp,其中dp[i]表示構成數字i所需的最小完全平方數數量。因此,我們需要填充整個dp數組來解決問題。初始化dp[0] = 0,因為0不需要任何完全平方數就可以得到。然後,我們將填充dp數組的其餘部分。對於i > 0,dp[i]的值可以通過考慮i – j*j(其中j*j是小於或等於i的最大平方數)並將1添加到結果來得到。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX); 
        dp[0] = 0;  // 初始值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                dp[i] = min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};