硬币找零理解为一个DP的解决方案

“您将得到不同的教派和金额的总量的硬币写一个函数来计算的最少数目的需要硬币以弥补这个数额，如果这些数额的金额不能由任何硬币组合来补偿，则返回-1。“

例1：

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

而且我也用Google搜索这样一个解决方案：

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？

任何人都可以用简单的英语表达出路吗？

来源

2016-01-13 Omg I killed Kennny

你有没有了解'dp'数组存储的内容？如果你明白这一点，算法非常简单。 –

您的导师希望您从头开始编写解决方案，而不是Google提供解决方案。这样你可能会学到一些东西。 – Raedwald

它让我感到这个问题得到了4票。 – Raedwald

好吧，让我们先看看代码在做什么以及它在使用什么。 DP用于存储特定值所需的硬币数量。它是这样做的，以便获得一个值所需的硬币数量只是“价值dp的入口”。但是，我们如何获得有序的金额清单？

他重复了他使用inner for循环的所有硬币，试图将硬币的值添加到当前值（i）。如果这小于目标数量，他会为其分配一个值。

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

我们知道，我们的名单是由值排序，我们会得到我们需要利用我们当前的记录（Ⅰ）加上当前硬币的价值的价值来改变项的值（硬币[J]）。这是它的左边部分。

现在对于正确的部分：您正在寻找尽可能小的数量，因此您使用Math.Min来获取n个参数中的较小者，在这种情况下为两个。第一个参数是我们将要覆盖的值。如果我们已经找到了表示值的真正好方法，为什么要重写它呢？我们可能会意外地杀死它，所以我们确保只有当我们找到的解决方案不比我们得到的更好时才这样做。第二个说法就是，我们需要得到的电流值的硬币的量+ 1

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

如果你还没有完全了解它尚未随时要求进一步的细节:)

来源

2016-01-13 09:13:27 Pepich1851

Thx！所以在大多数情况下，“dp [i] + 1”将是“dp [i + coins [j]]”的值？所以，如果我理解正确，那么程序实际上列出了价值低于金额的硬币组合的所有可能性？ –

是的，它会首先计算所有可能的值和他们的最佳解决方案，以最终找到您的价值的最佳解决方案。这被称为贪婪算法，这是一个非常低效的算法。 – Pepich1851

意外击中输入两次，所以另一个评论是。 “dpi [i] + 1”和dpi [i +硬币[j]]“不需要相同，只是在那里检查这两种方式的更好。这可能是你已经找到了一个好方法，你不想失去这个价值，所以你走了，只是把这两个选项中的更好，因为两者都是可能的:) – Pepich1851

硬币找零理解为一个DP的解决方案

回答

相关问题