1000ms

Difficulty: 6

所属公司 : Hot100

算法与标签>动态规划

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

题目内容

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

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

输入描述

一个整数 $n$

输出描述

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

样例1

输入

输出

说明

$12 = 4 + 4 + 4$

样例2

输入

输出

说明

$13 = 4 + 9$

提示：

$1 <= n <= 10^4$