leetcode 279 : 完全平方数(面试时遇到)

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例1：

Input: n =12
Output: 3
12 = 4 + 4 + 4

示例2：

Input: n =13
Output: 2
13 = 4 + 9

解法一

看到题目以后，最直观的思路就是暴力去试，用深度搜索去做。
但当数字过大时会超出时间限制。

    int numSquares(int n) {
        unordered_set<int> squares;
        for(int i=1; i<=sqrt(n); ++i)
        {
            squares.insert(pow(i,2));
        }
        return minnumSquares(n, squares);
    }
    int minnumSquares(int n,const unordered_set<int> & squares)
    {
        if(squares.count(n))
        {
            return 1;
        }
        int minnum = INT_MAX;
        for(const auto & square : squares)
        {
            if(n > square)
            {
                minnum = min(minnum, minnumSquares(n-square, squares)+1);
            }
        }
        return minnum;
    }

解法二

参考链接:link
用广度优先搜索去做，输出第一次构成结果时的层数。
广度优先搜索示意图

   int numSquares(int n) {
        unordered_set<int> visited;
        queue<int> q{{0}};
        int steps = 1;
        while (!q.empty()) {
            auto size = q.size();
            while (size--) {
                auto cur = q.front(); q.pop();
                for (int i = 1; i * i + cur <= n; i++) {
                    auto next = i * i + cur;
                    if (next == n) {
                        return steps;
                    }
                    if (!visited.count(next)) {
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
            steps++;
        }

        return -1; // should never reach here.
    }

解法三

利用动态规划去做，思路如下:
题目的要求是需要找出多少个数的平方来表示整数 $n$ 。
这些数必然会落在区间 $\sqrt{n}]$ ，因此可以枚举这些数，假设当前枚举到 $j$ ,呢么还需要取若干个数的平方构成 $n - j^2$ 。此时发现该子问题和原问题类似，只是规模变小了。这符合动态规划的要求，于是可以写出状态转移方程:
$min_{j=1}^{\lfloor \sqrt{n} \rfloor} f[ n-j^2 ]$
其中 $f [0] = 0$ 为边界条件，实际上无法表示数组 $0$ ，只是为了保证状态转移过程中遇到 $j$ 恰为 $\sqrt{n}$ 的情况合法。
计算 $f [n]$ 时所需要用到的状态仅为 $f [ n-j^2 ]$ ，必然小于 $n$ ，因此只需要从小到大地枚举 $n$ 来计算 $f [n]$ 即可。

int numSquares(int n)
{
	vector<int> dp(n+1);
	for(int i=1; i<= n; ++i)
	{
		int minn = INT_MAX;
		for(int j=1; j * j <= i; ++j)
		{
			minn = min(minn, dp[i - j * j]);
		}
		dp[i] = minn + 1;
	}
	return dp[n];
}