05.03.07-Exercises.md

05.03.07 练习题目（第 07 天）

1. 0279. 完全平方数

1.1 题目大意

描述：给定一个正整数 $n$。从中找到若干个完全平方数（比如 $1$、$4$、$9$、$16…$），使得它们的和等于 $n$。

要求：返回和为 $n$ 的完全平方数的最小数量。

说明：

• $1 \le n \le 10^4$。

示例：

• 示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

• 示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

2. 0322. 零钱兑换

2.1 题目大意

描述：给定代表不同面额的硬币数组 $coins$ 和一个总金额 $amount$。

要求：求出凑成总金额所需的最少的硬币个数。如果无法凑出，则返回 $-1$。

说明：

• $1 \le coins.length \le 12$。
• $1 \le coins[i] \le 2^{31} - 1$。
• $0 \le amount \le 10^4$。

示例：

• 示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

• 示例 2：

输入：coins = [2], amount = 3
输出：-1

3. 0518. 零钱兑换 II

3.1 题目大意

描述：给定一个整数数组 $coins$ 表示不同面额的硬币，另给一个整数 $amount$ 表示总金额。

要求：计算并返回可以凑成总金额的硬币方案数。如果无法凑出总金额，则返回 $0$。

说明：

• 每一种面额的硬币枚数为无限个。
• $1 \le coins.length \le 300$。
• $1 \le coins[i] \le 5000$。
• $coins$ 中的所有值互不相同。
• $0 \le amount \le 5000$。

示例：

• 示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

• 示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3。

习题解析

1. 「0279. 完全平方数」习题解析：网页链接、Github 链接
2. 「0322. 零钱兑换」习题解析：网页链接、Github 链接
3. 「0518. 零钱兑换 II」习题解析：网页链接、Github 链接