[Leetcode]279. Perfect Squares(C++)

题目描述

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

例子

例子 1

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

例子 2

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

解题思路

这道题可能一下子想不到用动态规划来做。但是如果如果我们把 (1 ～ n) 中任意一个数看成 n = a + b；那么就可以求解 min_nums(n) = min_nums(a) + min_nums(b)，因此我们只要遍历所有的相加组合，进行最小化更新即可。而在这其中，由于要考虑的是平方数相加，所以我们只需要更新包括平方数相加的组合，具体如下：

#include <limits.h>

#include <cmath>
#include <vector>
class Solution {
public:
    int numSquares(int n) {
        std::vector<int> num_squares(n + 1, INT_MAX);
        num_squares[0] = 0;

        // 遍历所有 sqrt(n) 用来构造平方数
        for (int i = 1; i <= std::sqrt(n); ++i) {
            for (int j = 1; j <= n; j++) {
                // 对每一个大于 i * i 的数，有以下相加组合：
                // a = i * i, b = j - i * i, j = a + b
                // num_squares[j] = num_squares[a] + num_squares[b]
                //                = 1 + num_squares[j]
                if (j - i * i >= 0) {
                    num_squares[j] =
                        std::min(num_squares[j], 1 + num_squares[j - i * i]);
                }
            }
        }
        return num_squares[n];
    }
};

时间复杂度: O(n*sqrt(n))
空间复杂度: O(n)

GitHub 代码同步地址： 279.PerfectSquares.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions