1000ms

Difficulty: 6

所属公司 : Hot100

算法与标签>动态规划

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（面试手撕 LC Hot 100(ACM模式版)），可解锁完整内容。

购买题库开通会员

思路

将要组成的整数 $n$ 看成长度为 $n$ 的木板，完全平方数 $x^2$ 看成长度为 $x^2$ 的木板。

问题转化成：将一个长度 $n$ 的木板分割成最少的部分，要求每个部分的长度恰好是完全平方数。

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$