LeetCode322零钱兑换DFS优化：rem/coin>min_cost为何可中断循环？

先明确前提：

• 硬币数组已按降序排序，从大面值硬币开始尝试
• min_cost是当前已找到的「凑出目标金额所需的最小硬币数」（初始值通常设为目标金额+1这类极大值）
• rem是当前还需凑的剩余金额
• coin是当前遍历到的硬币面值

优化逻辑的核心：提前剪去不可能更优的分支 #

当判断rem / coin > min_cost时直接break，跳过当前硬币之后的所有更小面值硬币，原因如下：

1. rem / coin的含义：这是仅用当前面值硬币凑完剩余金额的理论最小硬币数下限（能整除时为rem//coin，不能整除时为rem//coin + 1，即向上取整后的结果，rem/coin是该下限的浮点数形式）。
2. 硬币已降序排序，后续硬币面值更小，用更小面值凑rem需要的数量只会比rem/coin更多（面值越小，凑同等金额所需数量越多）。
3. 如果连「用当前最大面值硬币凑rem的理论最小数量」都超过了当前最优解min_cost，那用任何更小面值硬币去凑，结果只会更差，不可能得到比min_cost更优的解——直接break终止后续遍历，避免无效递归。

关于dfs(rem-coin) + 1 >= rem / coin的推导 #

dfs(rem-coin) + 1是「用1枚当前硬币后，凑剩余金额rem-coin的最优解加1」，它必然大于等于rem / coin，推导如下：

• 对于剩余金额rem-coin，无论用什么硬币组合，所需硬币数至少是凑出rem-coin的理论最小数量，即ceil((rem-coin)/coin)（当前硬币是最大面值，用它凑rem-coin所需数量最少）。
• 计算可得：ceil((rem-coin)/coin) = ceil(rem/coin - 1)，结果等于ceil(rem/coin) - 1（当rem不是coin的倍数时），或(rem/coin) - 1（当rem是coin的倍数时）。
• 因此dfs(rem-coin) + 1 >= ceil(rem/coin) - 1 + 1 = ceil(rem/coin)，而ceil(rem/coin)本身就大于等于rem/coin（向上取整结果不会小于原数）。
• 也就是说，dfs(rem-coin)+1的实际结果不会比「仅用当前硬币凑rem的理论最小数量」更少，当rem/coin已经超过min_cost时，这条分支必然无法得到更优解，完全可以剪去。

内容的提问来源于stack exchange，提问作者figs_and_nuts