c++ - 递归算法时间复杂度 : Coin Change

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;
}

然后我意识到“接受”的解决方案如下:

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) 时间内运行并使用 O(n) 内存，并且非常简洁——在大小上与您的天真递归解决方案相当。 https://stackoverflow.com/a/20743780/1400793 .它是用 Python 编写的，但可以轻松转换为 C++。