c++ - 关于 c++ 中问题的最小函数（CP 和动态编程）

Question

这是一个解决需要多少硬币才能形成特定数字的函数。IE 我们想用 {1, 2, 3, 4, 1, 1} 个硬币形成总和 6。组成 6 所需的最少硬币数量是多少？DP(Dynamic Programming)中的最优解：4+2

问题是为什么我们将一个数字与无穷大进行比较？在 for 循环中的最佳变量中。

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;
}

标签： c++

Answer 1

INFINITY是可用的最高数值浮点值。这意味着，每个数字都应该小于无穷大。由于best需要在使用前进行初始化，所以将其初始化为最大值是最有意义的。