P153. 最少完全平方数分解

leetcode 279 lintcode 513 动态规划 数学 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一个正整数 n,你要计算出它最少可以分解成多少个完全平方数的和。完全平方数指的是可以表示成某个整数的平方的数字,比如 1、4、9、16 等等。

比如说,给你的 n 等于 5。5 最少可以表示成 1 和 4 这两个完全平方数相加:

5 = 1 + 4

因此 5 最少可以分解成 2 个完全平方数的和。

再比如说,给你的 n 等于 12。它最少可以分解成 4 + 4 + 4:

12 = 4 + 4 + 4

因此 12 最少可以分解成 3 个完全平方数的和。

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。