题目

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;

    }

};