二元规划-换币问题

Question

我正在解决以下问题从hackerrankhttps://www.hackerrank.com/challenges/coin-change/problem

我无法解决这个问题，所以我看了社论，他们提到

T（i， m）=T（i， m-i）T（i 1， m）

我无法从整体上理解为什么这个解决方案在更高的层次上有效。（如CLRS中的证明或简单易懂的示例）

我写的解决方案如下

fun(m){
 //base cases
 count = 0;
 for(i..n){
  count+= fun(m-i);
 }
}

我的解决方案不起作用，因为有一些重复的调用。但是编辑是如何工作的，以及我的解决方案和更高层次的编辑之间的区别是什么...

Answer 1

我认为，为了让它起作用，你必须清楚地定义T是什么。也就是说，我们将T（i，m）定义为仅使用索引至少为i的硬币对m个单位进行更改的方式的数量（即，我们只查看第i个硬币，第（i 1）个硬币，一直到第n个硬币，而忽略第一个i-1硬币）。此外，我们定义了一个数组C，使得C[i]是第i枚硬币的值（注意，通常C[i]与i不同）。因此，如果有n个硬币（即C的长度为n），并且我们想要对W单位进行更改，我们将寻找值T（0，W）作为我们的答案（确保您可以看到为什么此时会出现这种情况！）。

现在，我们继续构造T（i，m）的递归定义。请注意，我们的解决方案要么包含一个额外的第i个硬币，要么不包含。如果它包含，我们的新目标将只是m-C[i]，对此进行更改的方法的数量是t（i，m-C[i]）（因为我们的新目标现在是C[i]小于m）。在另一种情况下，我们的解决方案不包含第i个硬币。在这种情况下，我们保持目标值相同，但只考虑指数大于I的硬币，即，在这种情况下，改变的方法的数量是T（i 1，m）。由于这些情况是不相交且详尽的（要么在解决方案中放入第i个硬币，要么不放入！），我们有

T(i,m) = T(i, m-C[i]) + T(i+1,m)

这与你的情况非常相似（C[i]的差异很重要）。注意，如果m

现在仍然需要计算T（0，W），您可以轻松地递归地进行计算。然而，您可能注意到许多子问题被重复，这使得这是一个缓慢的解决方案。解决方案是使用一种叫做动态编程或记忆的方法。即，每当计算一个解时，将其值添加到一个表中（例如，T[i，m]，其中T是一个nxw大小的二维数组）。然后，当你递归地计算某个东西时，首先检查表，这样你就不会对同一个东西计算两次。这就是所谓的回忆录。动态规划很简单，除非你有一点远见，按照需要的顺序来计算。例如，我将首先计算基本情况，即列T[，0]。然后，我将根据递归定义计算与该行和该列相邻的所有值。