递归算法时间复杂度：换币

Question

我正在研究一些算法，遇到了 coin change 问题。

在思考这个问题时，我想到了这个简单的递归解决方案：

int coinChange(const vector<int>& coins, int start, int n) {
  if (n == 0) return 1;
  if (n < 0) return 0;

  int total = 0;

  for (int i = start; i < coins.size(); ++i) {
    if (coins[i] <= n) total += coinChange(coins, i, n-coins[i]);
  }

  return total;
}

然后我意识到 "accepted" 解决方案如下：

int count( int S[], int m, int n )
{
    // If n is 0 then there is 1 solution (do not include any coin)
    if (n == 0)
        return 1;

    // If n is less than 0 then no solution exists
    if (n < 0)
        return 0;

    // If there are no coins and n is greater than 0, then no solution exist
    if (m <=0 && n >= 1)
        return 0;

    // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

起初我以为两者本质上是一样的。我很清楚我的递归树要宽得多，但这似乎只是因为我的算法在每一层做了更多的工作，所以它变得平衡了。看起来这两种算法都在考虑用当前硬币进行更改的方法数量（假设它 <= 当前总和），并考虑在没有当前硬币的情况下进行更改的方法数量（因此所有元素都在硬币数组减去当前硬币）。因此，我算法中的参数 start 与第二个算法中的 m 所做的基本相同。

不过我越看越觉得不管前面的文字如何，我的算法是O(n^n)，第二个是O(2^n)。我已经关注这个太久了，但如果有人可以解释我的算法与第二个算法相比做了哪些额外的工作，那就太好了。

编辑

我了解这道题的动态规划解法，这道题纯粹是一道基于复杂度的题。

Answer 1

除了第二段代码使用递归而不是 for 循环来迭代硬币外，这两段代码是相同的。这使得它们的运行时间复杂度相同（尽管由于额外的递归调用，第二段代码可能具有更差的内存复杂度，但这可能会在清洗过程中丢失）。

例如，这是在 S = [1, 5, 10] 且 m=3 的情况下对第二个 count 的部分评估。在每一行上，我扩展 count.

最左边的定义

  count(S, 3, 100)
= count(S, 2, 100) + count(S, 3, 90)
= count(S, 1, 100) + count(S, 2, 95) + count(S, 3, 90)
= count(S, 0, 100) + count(S, 1, 99) + count(S, 2, 95) + count(S, 3, 90)
= 0 + count(S, 1, 99) + count(S, 2, 95) + count(S, 3, 90)

您可以看到，这与计算 total 的 for 循环相同。

这两种算法都很糟糕，因为它们运行在指数时间内。这是一个（我的）答案，它使用一种简洁的动态编程方法，在 O(nm) 时间内使用运行s 并使用 O(n) 内存，并且非常简洁——在大小上与你的天真递归解决方案相当. 。它在 Python 中，但它可以简单地转换为 C++。

Answer 2

您没有阅读整篇文章 (?)。

动态规划背后的思想是存储一些已经获得的值，这样就不需要再次计算它们。在文章的最后你可以看到实际正确的解决方案。

至于为什么你的解是n^n，而他们原来的解是2^n。这两种解决方案实际上都是 2^(n+#coins)。他们只是用 m-1 调用函数，而不是让一个循环遍历每个硬币。虽然您的解决方案从一开始就尝试每枚硬币，然后越来越少，但他们的解决方案尝试使用一个类型为 m 的硬币，然后是另一个，然后是另一个，直到在某个时候它切换到类型 m-1 并对其执行相同的操作等等在。基本上两种解决方案都是一样的。

另一种证明它们具有相同复杂度的方法是这样的：

两个解决方案都是正确的，因此它们将达到所有可能的解决方案，并且在达到负 n 时都停止增长递归的特定分支。因此，它们具有相同的复杂性。

如果您不相信，请尝试每个解决方案，除了添加一些计数器并在每次输入函数时递增它。对每个解决方案执行此操作，您将看到获得相同的数字。

Answer 3

基准在我的计算机上的基准测试如下：

coinChange(v, 0, 500);// v=[1, 5, 10, 15, 20, 25]

用了 1.84649 秒完成。但是

count(s, 6, 500); //s = [1, 5, 10, 15, 20, 25]

执行时间为 0.853075 秒。
编辑
我将结果解释为两种算法的时间复杂度相同。

递归算法时间复杂度：换币

Recursive Algorithm Time Complexity: Coin Change

c++

algorithm

recursion

time-complexity

coin-change

编辑