完全背包

题目要求 给定一个正整数 n，返回若干个正的完全平方数相加得到 n 时，所需的最少数量。完全平方数是整数的平方，例如 1 = 1²、4 = 2²、9 = 3²、16 = 4²。 和必须刚好等于 n。 同一个完全平方数可以使用任意次。 只返回数量，不需要返回具体分解；加数的先后顺序不影响答案。 约束：1 <= n <= 10^4。 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4，需要 3 个完全平方数。 输入：n = 13 输出：2 解释：13 = 9 + 4，需要 2 个完全平方数。 下面使用 Python 3.9+ 逐步构建解法，适合已经理解函数、循环和基础递归，希望进一步理解动态规划的读者。 Step 1：先确定剩余和为 0 的答案 先拿最大的平方数，会不会让数量最少？对 n = 12，这一选择得到： 12 -> 先拿 9 -> 剩下 3 -> 再拿 1 + 1 + 1 总共：9 + 1 + 1 + 1，4 个 但是 4 + 4 + 4 只需要 3 个。当前的想法是“每次选不超过剩余和的最大平方数”，它在 12 上已经失败：单次拿得更多，不保证最后用得更少。 ...

题目要求 给定一个整数数组 coins，其中 coins[i] 是一种硬币的面额；再给定一个非负整数 amount，要求凑出刚好等于 amount 的金额。 每种硬币都可以使用任意次。 返回凑出 amount 所需的最少硬币数量。 如果无法凑出，返回 -1。 如果 amount = 0，不需要使用硬币，答案是 0。 约束是：1 <= coins.length <= 12、1 <= coins[i] <= 2^31 - 1、0 <= amount <= 10^4。硬币面额互不相同。 例如： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：5 + 5 + 1 一共使用 3 枚硬币。 输入：coins = [2], amount = 3 输出：-1 解释：只使用面额 2 无法凑出 3。 输入：coins = [1], amount = 0 输出：0 解释：目标金额已经是 0，不需要再选硬币。 Step 1：先把目标金额拆成更小的问题 先看一个会逼出问题结构的小例子： ...