leetcode-279

题目

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example1

1
2
3

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

Example2

1
2
3

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

分析

这道题目的意思是给定一个正整数，要求我们找到最少的平方数，它们的和等于这个正整数。

解法一

一开始我尝试从这个正整数减去它最大的平方数入手，判断剩下的数能由多少个平方数组成。但这样做的问题是很可能找不到最少的平方数数目，因为剩下那部分数可能只能由1组成，比如12按这种做法得到的结果就是4。

对于这种问题，最好的方法是分解问题成为一个个易求解的子问题，再分别求解。

我分解问题的方法其实也是在前面的想法上进行改进得到的。

假设问题要求解的是num[n]，n为输入的正整数，我们可以把问题分解成：

1	num[n] = min(num[n], num[n - i * i] + 1)

其中i是范围在[1, sqrt(n)]的正整数。通过赋值num[0] = 0，我们可以求出很多num[平方数] = 1，这样一层层求解出来就可以得到num[n]了。

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> num(n + 1, __INT_MAX__);
        num[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= sqrt(i); ++j) {
                num[i] = min(num[i - j * j] + 1, num[i]);
            }
        }
        return num[n];
    }
};

解法二

解法二是我在Discuss中看到的，是一种数学解法，利用到了四平方和定理，简单来说就是任何一个正整数都可以表示成4个平方数之和，因此答案 <= 4。同时这个定理中还有一个公式：4^k(8m + 7)，如果一个正整数不满足这个公式，那么它可以表示成3个平方数之和，此时答案 <= 3；反之，满足这个公式的话答案 == 4。还有个重要的性质：就是如果一个数n是4的倍数，那么num[n] = num[n / 4]。

利用这个数学定理，我们可以更加快速地求出这个问题的答案，利用最后那个性质可以把正整数n缩小，很大地简化了后续求解过程。

代码

#include <iostream>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        //是4的倍数的话可以除以4，不影响结果
        while (n % 4 == 0) n /= 4;
        //满足8m + 7的数
        if (n % 8 == 7) return 4;
        else {
            //能否拆成两个平方数之和
            for (int i = 0; i * i <= n; ++i) {
                int tmp = sqrt(n - i * i);
                if (tmp * tmp == n - i * i) {
                    return !!i + !!tmp;
                }
            }
            //拆不了的话答案就一定是3
            return 3;
        }
    }
};