您现在的位置是：首页 >技术杂谈 >LeetCode279之完全平方数(相关话题：动态规划，四平方和定理)网站首页技术杂谈

LeetCode279之完全平方数(相关话题：动态规划，四平方和定理)

击水三千里 2023-07-08 16:00:02
简介LeetCode279之完全平方数(相关话题：动态规划，四平方和定理)

题目描述

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

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

示例 1：

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

示例 2：

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

方法一（动态规划） 

f[i]表示最少需要多少个数的平方来表示整数 i。

这些数必然落在区间 [1,sqrt{n}]。我们可以枚举这些数，假设当前枚举到 j，那么我们还需要取若干数的平方，构成

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐