自下而上的方法，以减少硬币数量的变化

Question

我正在构建一种自下而上的方法来解决硬币兑换问题。我必须提供所需的最低硬币数量，以提供所需的零钱。可能由于给定的面额无法形成值，因此无法给出更改。

例如，如果给定的面额是{4,8}，他们要求改变5，那么就不可能给5。我构建了下面的程序，它适用于大多数情况，除非不可能形成所请求的更改。例如，当面值仅为{4}而我请求5时，它返回一个假值。我能做些什么来纠正这个问题？

这里P表示请求的更改，S是存储在数组中的面值[]的数目，从索引0到S-1。dp是一个二维数组，用于初始化为-1的计算。

for (int i = 0; i <= P; ++i) {
    for (int j = 0; j < S; ++j) {
        int ans, x, y;

        // Min. no. of coins with current coin
        x = (i - denominations[j] >= 0) ? dp[i - denominations[j]][j] + 1: 0;

        // Min. no. of coins w/o current coin
        y = (j > 0) ? dp[i][j - 1] : 0;

        ans = min(x, y);
        if (ans == 0) ans = max(x, y);
        dp[i][j] = ans;
    }
}

谢谢你的帮助。

Answer 1

错误在于，当禁止使用和不使用当前硬币时，您没有正确处理该情况。这发生在你的例子中，例如：当i=1和j=0时，我们试图不使用任何东西或仅使用一枚4c硬币来获得1c的总数；但是我们不能用4c币来做这件事，没有4c币也不行。

在这种情况下，x和y都将被指定为0，如果（ans==0）ans=max（x，y），则行 ，旨在捕捉禁止任何一种可能性时的情况，最终错误地将0分配给ans。随后的外循环迭代将“认为”有可能使相应的总和不包含任何硬币，并愉快地在此基础上加上1，为您的示例给出不正确的答案1。

我认为，最干净的修复方法是选择一个不同于0的sentinel值来表示“此操作是不可能的，不应考虑”。由于将这两种可能的操作与min（）组合在一起，因此一个非常高的值自然适合：

#define INF (INT_MAX-1)   // Or anything higher than the biggest sensible answer

for (int i = 0; i <= P; ++i) {
    for (int j = 0; j < S; ++j) {
        int ans, x, y;

        // Min. no. of coins with current coin
        x = (i - denominations[j] >= 0) ? min(INF, dp[i - denominations[j]][j] + 1) : INF;

        // Min. no. of coins w/o current coin
        y = (j > 0) ? dp[i][j - 1] : INF;

        ans = min(x, y);
        dp[i][j] = ans;
    }
}

请注意ans=min（x， y）；行现在给出了正确的答案，而无需进一步的工作，包括它应该是INF的情况，因为x和y都是INF。

更微妙的一点是，当我们在计算过程中读取一些dp[A][b]时，该值被允许为INF：这是一个合法值，表明A美分不能与任何类型的硬币组合