题解

题面描述

给定一个整数 $n$，要求返回和为 $n$ 的完全平方数的最少数量。
完全平方数 指的是形如 $k^2$ 的数，其中 $k$ 为整数。例如，$1$、$4$、$9$、$16$ 均为完全平方数，而 $3$ 和 $11$ 不是。

思路

Leetcode 84.完全平方数-原题链接

题目内容

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

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

输入描述

一个整数 $n$

输出描述

一个整数表示和为 $n$ 的完全平方数的最少数量

样例1

输入

12

输出

3

说明

$12 = 4 + 4 + 4$

样例2

输入

13

输出

2

说明

$13 = 4 + 9$

提示：

• $1 <= n <= 10^4$