【Day46】279. 完全平方数

279. 完全平方数

给定正整数 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

题解:

//假设最小公式值m = ƒ(n) 
//那么n的值满足下列公式 ∑(A[i] * A[i]) = n 
//令 k 为满足最小值 m 的时候,最大的平方数  。 令  d + k * k; = n ;  d >= 0; 
   // 注意:一定要是满足m最小的时候的k值,一味的取最大平方数,就是贪心算法了
//得出 f(d) + f(k*k) = f(n);
//显然 f(k*k) = 1; 则  f(d) + 1 = f(n); 因为 d = n - k*k;
//则可以推出ƒ(n - k * k) + 1 = ƒ(n) ;  且 k * k <= n;

class Solution {
public:
    int numSquares(int n) {
        if (n <= 0) return 0;
        std::vector nums(n+1);
        for(int i = 1; i <= n;i++)
        {
            int min = i;
            for(int j = 1;i - j*j >= 0;j++)
            {
                int tmp = nums[i-j*j] + 1;
                min = min > tmp ?  tmp:min; 
            }
            nums[i] = min;
        }
        return nums[n];

    }
};

   转载规则


《【Day46】279. 完全平方数》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day47】1449. 数位成本和为目标值的最大数字 【Day47】1449. 数位成本和为目标值的最大数字
1449. 数位成本和为目标值的最大数字给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数: 给当前结果添加一个数位(i + 1)的成本为 cost[i] (cost 数组下标从 0 开始)
2021-06-12
下一篇 
【Day45】518. 零钱兑换 II 【Day45】518. 零钱兑换 II
518. 零钱兑换 II给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方
2021-06-10
  目录