C++动态规划零钱兑换问题中为何将best初始化为INFINITY？

问题描述 #

这是一道用于求解组成特定金额所需最少硬币数的函数示例：例如使用硬币集合{1, 2, 3, 4, 1, 1}组成金额6，动态规划（DP）最优解为4+2，共需2枚硬币。对应C++实现代码如下：

int solve(int x)
{
    if (x < 0)
        return 100;
    if (x == 0)
        return 0;
    if (ready[x])
        return value[x];
    int best = INFINITY;
    for (int c : coins)
    {
        best = min(best, solve(x - c) + 1);
    }
    value[x] = best;
    ready[x] = true;
    return best;
}

请问上述代码的for循环计算最小硬币数时，为何要将变量best与INFINITY（无穷大）进行比较？

解答 #

这类最小值求解场景中，给存储最优结果的变量初始化为无穷大是非常通用的处理逻辑，具体到这段代码主要有两个核心作用：

• 保证最小值比较逻辑正常运行：我们的目标是从所有可选硬币对应的方案里选出硬币数量最少的解，如果best初始值设置得比所有合法解都小（比如设为0），后续min函数的比较结果会永远停留在初始值，根本得不到正确结果。而这里的INFINITY是预先定义的、比当前问题所有可能的合法解都大的数值，比如本题中如果最高需要凑的金额是100，全用1元硬币最多也只需要100枚，那INFINITY只要设为大于100的数即可，第一次计算出的合法硬币数就能直接替换初始值，后续遍历其他硬币时也能正常比较得到更小的最优解。
• 标识无法凑出金额的非法情况：如果遍历完所有硬币后best的值仍然等于INFINITY，就说明不存在任何硬币组合可以凑出当前金额x，后续逻辑可以直接通过这个特征判断非法场景，也能避免无效的非法值干扰上层递归的计算。

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