问题描述
近期，黄开的银行新发行了一种面额为 4 的钞票，使得钞票种类增至 5 种：20、10、5、4 和 1 元。银行在发钞时十分“节俭”，当有客户取钱时，需要以最少的钞票数来满足取款金额。 问题要求： 对于给定的金额 n（1 ≤ n ≤ 10000），求出凑成该金额所需的最少钞票数量。
输入格式： 输入包含不超过 10 组测试数据，每组数据给出一个整数 n。
输出格式： 对每组测试数据输出一个整数，表示最少所需钞票数。
输入样例：
2026
输出样例：
122
2. 动态规划核心思路
动态规划（DP）的核心思想是 记住历史，我们逐步计算 dp[i]，即金额 i 的最小钞票数。
关键步骤
1️⃣ 定义 dp 数组：
-
dp[i] = 凑出金额 i 的最少钞票数
2️⃣ 初始化：
-
dp[0] = 0（凑 0 元需要 0 张钞票） -
其余初始值设为
∞（表示不可达）
3️⃣ 状态转移方程： 对于每个金额 i 和面额 coin：
if i >= coin:dp[i] = min(dp[i], dp[i - coin] + 1)
即当前金额的最优解 = 使用 coin 面额后的剩余金额的解 + 1。这意味着：使用一张面额为 coin 的钞票后，剩余金额 i - coin 的最优解加上这张钞票即为候选答案。
代码实现
以下给出完整的 Java 实现示例：
import java.util.Scanner;import java.util.Arrays;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int[] coins = {20, 10, 5, 4, 1}; // 钞票面额while (scanner.hasNext()) {int n = scanner.nextInt();int[] dp = new int[n + 1]; // dp 数组，用于存储各金额所需的最少钞票数// 初始化 dp 数组Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0; // 0 元不需要钞票// 状态转移：从 1 到 n 逐步求解for (int i = 1; i <= n; i++) {for (int coin : coins) {if (i >= coin && dp[i - coin] != Integer.MAX_VALUE) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}// 输出金额 n 所需的最少钞票数System.out.println(dp[n]);}scanner.close();}}
💡 代码亮点：
-
面额降序排列：优先尝试大面额，减少计算次数
-
边界检查：确保
dp[i - coin]有效
示例解析
以样例输入 6 为例，详细说明动态规划过程：
-
初始化：
dp[0] = 0，其余dp[1...6]均初始化为无穷大。 -
计算 dp[1]：
-
只有使用 1 元钞票：
dp[1] = dp[0] + 1 = 1。
-
-
计算 dp[2]：
-
使用两张 1 元：
dp[2] = dp[1] + 1 = 2。
-
-
计算 dp[3]：
-
使用三张 1 元：
dp[3] = dp[2] + 1 = 3。
-
-
计算 dp[4]：
-
直接使用 4 元钞票：
dp[4] = dp[0] + 1 = 1； -
使用 1 元钞票方案为：
dp[4] = dp[3] + 1 = 4； 取较优解，故dp[4] = 1。
-
-
计算 dp[5]：
-
使用 5 元钞票：
dp[5] = dp[0] + 1 = 1； -
使用组合方案：4 + 1 元，
dp[5] = dp[1] + 1 = 2； 取较优解，故dp[5] = 1。
-
-
计算 dp[6]：
-
使用 5 元 + 1 元：
dp[6] = dp[1] + 1 = 2； -
使用 4 元 + 1 元 + 1 元：
dp[6] = dp[2] + 1 = 3； 取较优解，故dp[6] = 2。
-
最终，对于输入 6，答案为 2 张钞票（即 5 元 + 1 元）。
-
*复杂度分析
⏱️ 时间复杂度：
O(n × m)（m=面额数量）-
外层循环
n次，内层循环m次
💾 空间复杂度：
O(n)-
存储
dp数组
-
蓝桥杯备赛小贴士 🚀
1️⃣ 刷题技巧：
-
同类 DP 题目（背包、硬币问题）集中练习
-
先用小规模数据验证代码逻辑
2️⃣ 竞赛优化：
-
大面额优先：减少 DP 计算次数
-
预处理
dp数组：若多组查询，可全局计算一次dp[10000]
3️⃣ 常见误区：
-
未初始化
dp[0] = 0导致错误 -
漏掉面额可整除的情况（如
n=20直接返回1）
4️⃣ 延伸思考： ❓ 如果面额包含 7，最优解会如何变化？ （提示：6=5+1 vs 6=4+2→ 需重新推导 DP 表）
✏️ 互动：你在动态规划题中遇到过哪些难题？欢迎评论区讨论！👇
🔥 总结：本文通过 问题分析 → DP 建模 → 代码实现 → 优化技巧 完整解析了蓝桥杯高频题型，快来收藏练习吧！
