java - Coin Change 对 DP 解决方案的理解

Question

我有一个练习:

"You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1."

Example 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 循环遍历他拥有的所有硬币，试图将硬币的值(value)添加到当前值 (i)。如果它小于目标数量，他会为其分配一个值。

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

我们知道我们的列表是按值排序的，我们将通过获取当前条目 (i) 的值加上当前硬币的值 (coins[j] ).这是它的左边部分。

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

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

如果您还没有完全理解它，请随时询问更多详细信息:)