换钱问题

快速概览

换钱问题要求用最少数量的硬币凑齐给定的金额。它是理解动态规划（DP）优于贪心算法的典型案例。

贪心算法在某些币值组合下会失效
动态规划通过保存子问题的最优解来确保全局最优
它是序列比对、编辑距离等复杂 DP 算法的基础

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

问题定义

输入：

目标金额 $M$
可用的硬币面值集合 $c = \{c_1, c_2, \dots, c_d\}$

输出：

凑齐金额 $M$ 所需的最少硬币总数。

在算法页语境里，这个问题通常被写成优化版本：

若金额无法被给定面值组合表示，返回”不可达”；
若可达，返回最小硬币数。

贪心算法的失效

在日常生活中（如人民币或美元币制），贪心算法（优先使用最大面额）通常有效。但在生物信息学模拟的特殊”币制”下，贪心往往得不到最优解。

示例：

金额 $M = 40$
币值 $c = \{25, 20, 1\}$

贪心解：

取 25: 剩余 15
取 15 个 1: 总计 16 枚硬币

最优解：

取 2 个 20: 总计 2 枚硬币

动态规划解法

动态规划的核心是将大金额 $M$ 的问题分解为小金额 $m < M$ 的子问题。

状态转移方程

设 $dp[m]$ 为凑齐金额 $m$ 所需的最少硬币数：

$dp[m] = \min_{i} \{ dp[m - c_i] + 1 \}$

其中 $c_i$ 是所有满足 $c_i \leq m$ 的硬币面值。

算法步骤（Pseudocode）

CHANGE(M, c)
1  dp[0] ← 0
2  for m ← 1 to M
3      dp[m] ← ∞
4      for i ← 1 to d
5          if m ≥ c[i]
6              if dp[m - c[i]] + 1 < dp[m]
7                  dp[m] ← dp[m - c[i]] + 1
8  return dp[M]

示例

给定：

$M = 11$
$c = \{1, 3, 5\}$

按 $m = 1 \to 11$ 递推：

$dp[1]=1$ （1）
$dp[2]=2$ （1+1）
$dp[3]=1$ （3）
$dp[4]=2$ （3+1）
$dp[5]=1$ （5）
$dp[6]=2$ （3+3 或 5+1）
…
$dp[11]=3$ （5+3+3）

因此最优解为 3 枚硬币。

复杂度与适用前提

时间复杂度： $O(M \times d)$
空间复杂度： $O(M)$

适用前提：

金额 $M$ 规模可接受（非常大时需要进一步优化或近似策略）。
面值集合固定且可重复使用（unbounded knapsack 语义）。
目标是”最少数量”，不是”组合数量”或”是否可达”。

生物信息学关联

为什么在生物信息学 wiki 中讨论换钱问题？

算法启蒙：它是理解”局部最优不等于全局最优”的最简模型。
序列比对的影子：换钱问题在 1D 轴上移动，而序列比对是在 2D 矩阵上移动。本质上，序列比对是在寻找”凑齐两个序列重合度”的最优路径。
得分系统：在比对算法中，不同的碱基匹配或错配可以看作不同的”币值”或”权重”。

与真实工具或流程的连接

在读段比对（read alignment）中，动态规划矩阵本质上也是”从子问题累积到全局最优”的过程。
在组装和注释中，很多打分函数都可抽象为”有限动作集合 + 最优子结构”的 DP 模式。
当状态空间扩大到二维/三维时，换钱问题提供的是”如何定义状态和转移”的最小可用范式。