递归算法时间复杂度:硬币变化

Question

我正在通过一些算法,并遇到了硬币更改问题.

在思考这个问题时,我想出了这个天真的递归解决方案:

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 循环来迭代硬币。这使得它们的运行时复杂性相同（尽管第二段代码可能由于额外的递归调用而具有更差的内存复杂性，但这可能会在清洗中丢失）。

例如，这是count在 S = [1, 5, 10] 且 m=3 的情况下对第二个的部分评估。在每一行上，我都会扩展 的最左侧定义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)

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

这两种算法都很糟糕，因为它们的运行时间都是指数级的。这是（我的）一个答案，它使用一种简洁的动态编程方法，该方法在 O(nm) 时间内运行并使用 O(n) 内存，并且非常简洁——其大小与您的简单递归解决方案相当。/sf/answers/1452064631/。它是 Python 语言，但可以轻松转换为 C++。