网站 › 『编程语言区』 › 算法题-完全平方数 动态规划解法

dingallen216 发表于 2020-12-16 20:50

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

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


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

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

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

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

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

            if (dp == 1) continue;

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

      return dp;
    }
};

shujia2112 发表于 2020-12-17 00:25

{:1_926:}循环套循环直接导致性能严重下降

查看完整版本: 算法题-完全平方数 动态规划解法