LeetCode279 完全平方数 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。 示例 1： 输入：n = 12输出：3 解释：12 = 4 + 4 + 4 示例 2： 输入：n = 13输出：2解释：13 = 4 + 9 提示： 1 <= n <= 104 M

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13,

原问题：给定一个非负整数n，如果把它视作一些完全平方数的和，那么最少需要多少个完全平方数？ 这次学习到一个热心网友的解法：把问题转化兑换零钱问题，然后使用动态规划求解。 比如，给定 n=12, 那么我们可以列举出可能的完全平方数{1,4,9}。此时，如果把这些完全平方数视作可获得的硬币面值，把n视作待兑换零钱的总数，那么问题就是求“最少需要多少种硬币，能够把n换成零钱？如果兑换不成功，那么返回-

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 拉格朗日四平方和定理： 1、对于任意一个正整数都可以表示成至多四个整数的平方和(把0考虑进去了也)     下面剪枝性的来找对任意正整数n可以表示成多少几个整数的平方和 2、 若k%4=0

一、LeetCode322. 零钱兑换 题目链接：322. 零钱兑换 题目描述： 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amou