algorithm - 这个硬币找零算法的时间复杂度是多少？

Question

我解决了 leetcode https://leetcode.com/problems/coin-change-2/ 上的硬币兑换问题。

这是我写的代码:

    def change(self, amount: int, coins: List[int]) -> int:
        def helper(amount, coins, ind):
            if amount == 0:
                return 1
            if amount < 0:
                return 0
            if (amount, ind) in dp:
                return dp[(amount, ind)]

            res = 0
            for i in range(ind, len(coins)):
                res  += helper(amount - coins[i], coins, i)

            dp[(amount, ind)] = res
            return res

        coins.sort()
        dp = {}
        return helper(amount, coins, 0)

而且我注意到我在分析带有内存的算法的时间复杂性方面遇到了很多困难。例如，在这种情况下，我认为我们有 amount * number of coins 子问题 --> 因此算法在 O(amount * number of coins * number of coins) 中运行，我的因子中的第二个硬币数量来自这样一个事实，即对于每个子问题，我们必须通过循环 for i in range(ind, len(coins)): 来添加上结果。

然而，似乎这个解决方案实际上是我读到的 O(amount * number of coins) (自下而上的方法是 O(amount * number of coins) )。正确答案是什么？

我似乎对递归函数中的循环很挣扎，有时似乎我们将它们计入时间复杂度，而有时它们已经“计入”在子问题中，就像我怀疑这里的情况。

Answer 1

正如恩里科·博尔巴 (Enrico Borba) 评论的那样:

你的分析在我看来是正确的。您的表中有 O(amount * number of coins) 单元格，要计算表中的任何单元格，您运行循环(硬币数)次。您编写的代码具有这种复杂性。很可能有一种不同的算法具有 O(数量 * 硬币数量)复杂度。

— 恩里科·博尔巴