算法题-完全平方数 动态规划解法

dingallen216

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.


刷leetcode做到这道题的时候，第一反应是使用动态规划，写出来之后发现效率不佳，以为是哪里没有处理好，后来粘贴了几位大佬的dp算法，发现效率也不佳，才发现动态规划不是这道题最优解，但观感上我的代码还挺优雅，故来水个帖。

[C++] 纯文本查看 复制代码

class Solution {
public:
    int numSquares(int n) {

        vector<int> dp(n + 1, n);

        for (int i = 1; i * i <= n; i++) dp[i * i] = 1;

        for (int i = 2; i <= n; i++) {

            if (dp[i] == 1) continue;

            for (int j = 1; j * j < i; j++) {
                dp[i] = min(dp[i], dp[i - j * j] + dp[j * j]);
            }
        }

        return dp[n];
    }
};

shujia2112

循环套循环直接导致性能严重下降