279. 完全平方数

心已赠人 2022-10-06 05:42 310阅读 0赞

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

  1. class Solution {
  2. public:
  3.     int numSquares(int n) {
  4.         //无限背包
  5.         int d[10001] = {0};
  6.         d[0]=1;
  7.         int a[101],m=1;
  8.         while(m*m<=n)
  9.         {
  10.             a[m-1] = m*m;
  11.             m++;
  12.         }
  13.         m--;
  14.         for(int i = 0 ; i<m;i++)
  15.         for(int j = a[i];j<=n;j++)
  16.         {
  17.             if(d[j-a[i]]>0)
  18.             {
  19.                 if(d[j]>0)
  20.                 d[j] = min(d[j],d[j-a[i]]+1);
  21.                 else
  22.                 d[j] = d[j-a[i]]+1;
  23.             }
  24.         }
  25.         return d[n]-1;
  26.     }
  27. };

发表评论

表情：
评论列表 （有 0 条评论，310人围观）

还没有评论，来说两句吧...

相关阅读

    相关 279. 完全平方数

    给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 给你一个整数 n ，返回和为 n

    心已赠人心已赠人/ 0 赞/ 311 阅读