- 正确答案：零钱兑换问题（Coin Change）是经典的动态规划问题，核心目标是给定不同面额的硬币和一个总金额，求凑出该金额所需的最少硬币个数；若无法凑出则返回-1。其经典变式包括：1）零钱兑换II（求组合总数，顺序无关）；2）带限制的零钱兑换（每种硬币最多用k次）；3）恰好使用m枚硬币的方案数；4）输出所有可行解路径；5）最小硬币数且字典序最小的解。 - 解答思路：主问题（最小硬币数）采用自底向上DP：定义dp[i]为凑出金额i所需的最少硬币数，初始化dp[0]=0，dp[i]=+∞（或INT_MAX）表示不可达。对每个金额i，遍历所有硬币coin，若i≥coin且dp[i−coin]可达，则更新dp[i] = min(dp[i], dp[i−coin] + 1)。最终dp[amount]即为答案（若仍为初始不可达值则返回-1）。变式零钱兑换II（组合总数）则需改变状态定义与遍历顺序：dp[i]表示凑成i的组合数，初始化dp[0]=1，外层遍历硬币（保证每种硬币只选一次方向），内层遍历金额j=coin..amount，执行dp[j] += dp[j−coin]，避免重复计数排列（如[1,2]和[2,1]视为同一组合）。对于“恰好使用m枚硬币”的变式，需升维：dp[i][j]表示用j枚硬币凑出金额i的方案数，转移为dp[i][j] = sum_{coin} dp[i−coin][j−1]。若需输出所有解路径，须改用DFS+回溯，并配合剪枝（如当前硬币数已超最小解、剩余金额无法被最小面额整除等）。 - 深度知识讲解： 1）底层数据结构与状态设计本质：DP数组是一维/二维表，本质是记忆化搜索的空间显式展开。零钱兑换I中dp[i]的无后效性依赖于“最小硬币数”具有最优子结构——凑i的最优解必然由某个i−coin的最优解+1构成。 2）时间复杂度分析：基础DP为O(amount × coins.length)，空间可优化至O(amount)（一维滚动）。但注意：若硬币面额含1，则最坏需amount次迭代，此时amount极大时可能超时，需考虑数学优化（如贪心+验证，仅当硬币为标准货币系统如[1,5,10,25]时贪心正确）。 3）完全背包 vs 0-1背包视角：零钱兑换I和II均属“完全背包”问题（每种物品可无限使用），区别在于I求最小价值（硬币数），II求方案数。关键细节在于遍历顺序：求最值时内外循环可互换（但影响语义）；而求组合数时必须先遍历硬币再遍历金额，否则会将[1,2]和[2,1]视为不同方案（变成排列数）。 4）数值溢出与初始化陷阱：dp数组常初始化为INT_MAX或amount+1（因最多用amount枚1元硬币），更新时需判断dp[i−coin] != INT_MAX，否则INT_MAX+1会溢出。C++中可用LLONG_MAX，Java中用Integer.MAX_VALUE并用if (dp[j - coin] != Integer.MAX_VALUE) guard。 5）路径还原原理：在DP填表时同步维护parent[i]记录达到i时最后使用的硬币，或pre[i]记录前驱金额；也可在DP后逆推：从amount开始，找满足dp[i] == dp[i−coin] + 1的coin，加入路径并跳转至i−coin。 6）进阶变式底层机制： - “每种硬币最多用k次” → 转为分组背包，对每种coin拆成k个独立物品（但更优是三维DP：dp[i][j][t]表示前i种币、金额j、第i种用了t次）或二维优化：dp[i][j]表示金额j且第i种硬币已用次数，转移时枚举使用0~min(k, j/coin[i])次； - “字典序最小解” → 需贪心策略：从最大面额开始尝试，若使用该面额后剩余金额可被剩余硬币（含自身）凑出（可通过预处理canMake[j]布尔数组判断），则选择它，否则跳过。这要求预先计算“任意金额j是否可达”，可用BFS（类似最短路）或DP布尔数组实现。 - 代码示例（C++风格，零钱兑换I标准解法，含路径还原）： ``` int coinChange(vector& coins, int amount) { if (amount == 0) return 0; vector dp(amount + 1, amount + 1); // 初始化为不可能值（amount+1） vector parent(amount + 1, -1); // 记录上一状态 dp[0] = 0; for (int i = 1; i <= amount; ++i) { for (int coin : coins) { if (coin <= i && dp[i - coin] + 1 < dp[i]) { dp[i] = dp[i - coin] + 1; parent[i] = coin; } } } if (dp[amount] > amount) return -1; // 还原路径（可选） vector path; int cur = amount; while (cur > 0) { path.push_back(parent[cur]); cur -= parent[cur]; } // path即为一种最小硬币组合（顺序为使用顺序） return dp[amount]; } ``` - 变式零钱兑换II（组合总数）代码： ``` int change(int amount, vector& coins) { vector dp(amount + 1, 0); dp[0] = 1; for (int coin : coins) { // 外层硬币 for (int j = coin; j <= amount; ++j) { // 内层金额 dp[j] += dp[j - coin]; } } return dp[amount]; } ``` - 扩展知识：该问题与图论建模强相关——可将每个金额0..amount视为节点，对每个coin和每个i，添加有向边i→i+coin（权为1），则问题转化为求0到amount的最短路径长度（BFS适用，尤其当amount不大但coins稀疏时，BFS时间复杂度O(amount)，空间O(amount)）。此视角揭示DP本质是DAG上的最短路算法（因无环：边只从低金额指向高金额）。此外，在并发系统中，该模型可用于资源分配调度——硬币面额类比任务粒度，金额类比总资源需求，最小硬币数即最小调度单元数。

百度推荐算法日常实习一面分享

全站热榜

创作者周榜