对DP解决方案的硬币兑换理解

Question

我有一个练习：

您将获得不同面额的硬币和总金额。请编写一个函数来计算您需要的最少数量的硬币，以弥补该金额。如果硬币的任何组合都无法弥补该金额，请返回-1

例1：

     coins = [1, 2, 5], amount = 11
     return 3 (11 = 5 + 5 + 1)

我还谷歌了一个这样的解决方案：

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount + 1];
        final int INF = 0x7ffffffe;
        for (int i = 1; i <= amount; i++) dp[i] = INF;
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i + coins[j] <= amount)
                    dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

我知道它是关于DP的，但是，我对它很困惑，比如，DP[I coins[j]]的含义是什么，为什么要添加I，为什么要添加DP[I]1，为什么要添加1？

有人能用简单的英语指出出路吗？

Answer 1

好的，让我们首先看看代码在做什么，它在使用什么。DP用于存储特定值所需的硬币量。它这样做是有序的，所以得到一个值所需的硬币量只是“dp的值项”。但是我们如何得到那个有序的金额列表呢？

他正在使用内部for循环对所有硬币进行测试，试图将硬币的价值添加到当前价值（i）中。如果低于目标金额，他会给它赋值。

dp[i + coins[j]] = (...)

正如我们所知，我们的列表是按值排序的，我们将得到我们需要更改的条目的值，取当前条目的值（i）加上当前硬币的值（硬币[j]）。这是它的左边部分。

现在是正确的部分：你在寻找尽可能小的量，所以你在使用数学。min得到n个参数中较小的一个，在这种情况下是两个。第一个参数是我们将要覆盖的值。如果我们已经找到了一个非常好的方法来表示一个值，为什么要覆盖它？我们可能会不小心杀死它，所以我们确保只有当我们找到一个比我们得到的更好的解决方案时才会这样做。第二个参数是我们需要达到当前值1的硬币数量。

(...) = Math.min(dp[i + coins[j]], dp[i] + 1);

如果你还没有完全理解它，请随时要求进一步的细节：）