题目

ugly-number-ii

2. 算法

* 直接模拟

* DP

* dp优化

* 递归

3. 代码

* 直接模拟

class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return !!a + !!b;
            }
        }
        return 3;
    }
};

* dp

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

* dp优化

// DP
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(1, 0);
        while (dp.size() <= n) {
            int m = dp.size(), val = INT_MAX;
            for (int i = 1; i * i <= m; ++i) {
                val = min(val, dp[m - i * i] + 1);
            }
            dp.push_back(val);
        }
        return dp.back();
    }
};

* dp递归

// Recrusion
class Solution {
public:
    int numSquares(int n) {
        int res = n, num = 2;
        while (num * num <= n) {
            int a = n / (num * num), b = n % (num * num);
            res = min(res, a + numSquares(b));
            ++num;
        }
        return res;
    }
};